summaryrefslogtreecommitdiffstats
path: root/realloc.c
blob: faead2229c154d31f5f5b901492dc097b33702ec (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
/* ----------------------------------------------------------------------- *
 *   
 *   Copyright 2000-2008 H. Peter Anvin - All Rights Reserved
 *
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU Lesser General Public License as
 *   published by the Free Software Foundation, Inc.,
 *   59 Temple Place Ste 330, Boston MA 02111-1307, USA, version 2.1,
 *   incorporated herein by reference.
 *
 * ----------------------------------------------------------------------- */

/*
 * realloc.c
 *
 * Provice persistent storate version of realloc().
 *
 */

#include <assert.h>
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
#include <errno.h>

#include "lpsm.h"
#include "internals.h"
#include "bitops.h"

static void *lpsm_realloc_buddy(void *ptr, size_t new_size)
{
  struct buddy_params bp;
  int order, rorder;
  int xbit, obit, i;
  void *nptr;
  
  bp = lpsm_find_alloc_buddy(ptr);

  order = BUDDY_ORDER_MIN;
  while ( new_size > ((size_t)1 << order) )
    order++;

  if ( order > AH->arena_size_lg2 ) {
    /* Need to extend the arena immediately... */
    if ( lpsm_extend_arena(order+1) ) {
      errno = ENOMEM;
      return NULL;
    }
  }

  rorder = AH->arena_size_lg2 - order;

  DPRINTF(("buddy: realloc rorder %d %d -> rorder %d\n",
	   bp.rorder, bp.xbit, rorder));

  if ( rorder == bp.rorder ) {
    return ptr;			/* No change at all */
  } else if ( rorder > bp.rorder ) {
    /* Allocation shrink.  Return the extra space to the arena;
       no copy. */

    /*** FIXME: this could be bad for fragmentation if the
     *** allocation size delta is large.  Consider adding a
     *** heuristic copy to a less prime spot if delta is large. */

    /* Clear the old allocation size bit. */
    xbit = bp.xbit;
    clr_bit(AH->alloc_bitmap, xbit);

    /* Mark new buddies free */
    for ( i = bp.rorder+1 ; i <= rorder ; i++ ) {
      xbit <<= 1;
      set_bit(AH->free_bitmap, xbit^1);
      DPRINTF(("buddy: freing rorder %2d %8d\n", i, xbit^1));
    }

    /* Finally, mark new allocation size */
    set_bit(AH->alloc_bitmap, xbit);
  
    /* Nothing moved */
    return ptr;
  } else {
    /* Allocation enlargement.  Try to see if we can claim all the
       memory areas we need in order to avoid copying, otherwise
       get new allocation and copy. */

    size_t current_size = (size_t)1 << (AH->arena_size_lg2-bp.rorder);

    xbit = bp.xbit;
    for ( i = bp.rorder ; i > rorder ; i-- ) {
      if ( !test_bit(AH->free_bitmap, xbit^1) ) {
	/* A chunk we need is unavailable.  Need to copy, sorry... */
	DPRINTF(("buddy: unable to reallocate in place, rorder %2d %8d in use\n", i, xbit^1));

	/* Careful.  If lpsm_malloc_buddy resizes the arena we need to
	   adjust the rorder and xbit values afterwards. */
	nptr = lpsm_malloc_buddy(new_size);
	if ( !nptr ) {
	  errno = ENOMEM;
	  return NULL;		/* realloc failed */
	}

	memcpy(nptr, ptr, current_size);
	
	/* Free the old area */
	/* Consider later if we can optimize this given the resizing issue */
	lpsm_free_buddy(ptr);

	return nptr;
      }
      xbit >>= 1;
    }

    DPRINTF(("buddy: reallocating in place...\n"));

    /* Oh cool, we can expand in place */
    xbit = bp.xbit;
    
    /* Remove old allocation bit */
    clr_bit(AH->alloc_bitmap, xbit);

    /* Claim the memory */
    for ( i = bp.rorder ; i > rorder ; i-- ) {
      clr_bit(AH->free_bitmap, xbit^1);
      xbit >>= 1;
      DPRINTF(("allocated rorder %2d %8d\n", i, xbit^1));
    }

    /* Add new allocation bit */
    set_bit(AH->alloc_bitmap, xbit);

    /* Expansion in place is good, but we may still have to copy,
       since we might have been "high buddy" in one or more of the
       pairs we just claimed. */

    obit = 1 << rorder;
    nptr = (void *)((char *)AH->data_start +
		    ((uintptr_t)(xbit-obit) << order));

    if ( nptr != ptr ) {
      DPRINTF(("buddy: copying base from %p to %p\n", ptr, nptr));
      memcpy(nptr, ptr, current_size);
    }

    return nptr;
  }
}

static void *lpsm_realloc_slab(void *ptr, size_t new_size)
{
  struct slab_header *sh;
  struct slab_info *si;

  /* Slab header should be at the start of the page */
  sh = (struct slab_header *)((uintptr_t)ptr & ~(BUDDY_SIZE_MIN-1));
  assert(sh->magic == SLAB_MAGIC);

  si = &AH->slab[sh->index];

  DPRINTF(("slab: realloc %p size %d new_size %zu\n",
	   ptr, si->size, new_size));

  /* For realloc(), tolerate the size being off by as much as a
     factor of four... it's not worth copying then */
  if ( new_size > si->size ) {
    /* This also covers the possibility of new_size > slab_max */
    void *nptr = lpsm_malloc(new_size);
    if ( !nptr ) {
      errno = ENOMEM;
      return NULL;
    }
    memcpy(nptr, ptr, si->size);
    lpsm_free_slab(ptr);
    return nptr;
  } else if ( new_size < (si->size >> 2) ) {
    void *nptr = lpsm_malloc_slab(new_size);
    if ( !nptr )
      return ptr;		/* Old allocation still OK */
    memcpy(nptr, ptr, new_size);
    lpsm_free_slab(ptr);
    return nptr;
  } else {
    /* Nothing to do... */
    return ptr;
  }
}

void *lpsm_realloc(void *ptr, size_t new_size)
{
  int is_slab = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) != 0;
  int slab_max = AH->slab[0].size;

  /* Special cases for "realloc everything" style programming */
  if ( !ptr )
    return lpsm_malloc(new_size);
  else if ( new_size == 0 ) {
    lpsm_free(ptr);
    return NULL;
  }

  DPRINTF(("realloc: ptr = %p, new_size = %zu, is_slab = %d\n",
	   ptr, new_size, is_slab));

  if ( is_slab ) {
    /* lpsm_realloc_slab() also handles the slab->buddy case */
    return lpsm_realloc_slab(ptr, new_size);
  } else {
    /* Currently buddy. */
    if ( new_size > slab_max ) {
      return lpsm_realloc_buddy(ptr, new_size);
    } else {
      /* Buddy shrunk to slab size */
      void *nptr = lpsm_malloc_slab(new_size);
      if ( !nptr )
	return ptr;		/* Old allocation still OK */
      memcpy(nptr, ptr, new_size);
      lpsm_free_buddy(ptr);
      return nptr;
    }
  }
}