aboutsummaryrefslogtreecommitdiffstats
path: root/alloc.c
blob: 02087e608f02a7cb91bab3e9338e7858b839bc93 (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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
#ident "$Id$"
/* ----------------------------------------------------------------------- *
 *   
 *   Copyright 2000-2001 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 General Public License as published by
 *   the Free Software Foundation, Inc., 675 Mass Ave, Cambridge MA 02139,
 *   USA; either version 2 of the License, or (at your option) any later
 *   version; incorporated herein by reference.
 *
 * ----------------------------------------------------------------------- */

/*
 * alloc.c
 *
 * Provide persistent storage versions of malloc(), realloc() and free().
 *
 * This code uses a modified buddy system allocator for large allocations
 * and a SLAB allocator for small allocations.
 *
 * This generally assumes 8-bit bytes and 2's-complement arithmetric,
 * and that an all-zero bit pattern is a valid NULL.  These days, that's
 * oh-such-a-strech...
 */

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

#ifndef NDEBUG
#include <stdio.h>		/* For debugging printf() */
#define DPRINTF(X) printf X
#else
#define DPRINTF(X)
#endif

#include "objstore.h"
#include "internals.h"

static const unsigned char objstore_arena_magic[16] =
"\x4f\xd4\x5a\x16\xa0\xaf\xd5\x52\x56\xf1\x1c\x9c\x1c\xed\xcc";
static const unsigned char objstore_arena_zero[16] =
"\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";

#define SLAB_MAGIC		0xec2062ae

struct slab_info {
  int size;			/* Size of SLAB */
  int count;			/* SLABs per page */
  int data_offset;		/* Start of data area */
  struct slab_header *list;
};

/* This is 16 bytes on 32-bit and 24 bytes on 64-bit architectures */
/* This header must end aligned to a bitscan_t datum */
struct slab_header {
  uint32_t magic;
  uint16_t free_count;
  uint16_t index;		/* Index into slab_info array */
  struct slab_header *next, **rev;
};

#define SLAB_INFO_COUNT	32

/* Change these if BUDDY_ORDER_MIN or MINIMUM_ALIGN is changed */
/* These MUST be ordered in order of decreasing size.  0 is end of list. */
/* This particular set of slab sizes should work well for both a
   16- and 24-byte header size. */
static int slabsizes[] =
{
  2032, 1344, 1016, 800, 576, 448, 256, 192, 128, 96, 64, 48, 32, 16, 8, 4, 2, 1, 0
};

struct arena_header {
  unsigned char arena_magic[16];
  uint32_t arena_byteorder;
  uint16_t arena_bytesize;
  uint16_t arena_ptrsize;
  void *arena_base;		/* Base of allocation */
  void *free_bitmap;		/* The free bitmap */
  void *alloc_bitmap;		/* The allocated (buddy) bitmap */
  void *data_start;		/* Beginning of data area */
  int buddy_order_min;		/* Minimum size of buddy allocation */
  int arena_size_lg2;		/* Current arena allocation size */
  int header_size;		/* Size of this header+padding */
  struct slab_info slab[SLAB_INFO_COUNT];
  void *root_data_ptrs[ROOT_DATA_POINTERS]; /* Root data pointers - for the user */
};

/* This is the minimal order before going to SLAB allocation. */
#define BUDDY_ORDER_MIN		12
#define BUDDY_SIZE_MIN		(1U << BUDDY_ORDER_MIN)

/* Align allocations at least this large (2^n) to this boundary */
#define MINIMUM_ALIGN_LG2	4
#define MINIMUM_ALIGN		(1 << MINIMUM_ALIGN_LG2)
#define MINIMUM_ALIGN_MASK	(MINIMUM_ALIGN-1)

/* This is the size (2^n) allocated for a brand new arena.
   This allocation will be sparse, so don't freak out too much! */
#define ARENA_START_SIZE_LG2	17 /* 128K */
#define ARENA_START_SIZE	(1UL << ARENA_START_SIZE_LG2)

/* The data type to use for bitfield scanning.  Typically should equal
   the "natural" size on the machine, which used to always be "int".
   Unfortunately, that's no longer true... and getting all of these,
   including the value "bitscan_shift" doesn't seem to be feasible
   without external help. */
#ifdef BITSCAN_USE_UINT64
  typedef uint64_t bitscan_t;
# define BITSCAN_SHIFT		6
#else
  typedef uint32_t bitscan_t;
# define BITSCAN_SHIFT		5
#endif
#define BITSCAN_BITS		(1 << BITSCAN_SHIFT)
#define BITSCAN_MASK		(BITSCAN_BITS-1)
#define BITSCAN_0		((bitscan_t)0)
#define BITSCAN_1		((bitscan_t)1)

/*
 * These should be revamped to be thread-safe at some point.  That
 * may mean doing things that are architecture-specific...
 *
 * Important: "bit" can be negative, and that needs to be handled
 * correctly!
 */
static inline int test_bit(const void *ptr, int bit)
{
#if defined(__GNUC__) && defined(__i386__)
  int rv;
  asm("xorl %0,%0 ; btl %2,%1 ; adcl %0,%0"
      : "=&r" (rv) : "m" (*(const bitscan_t *)ptr), "r" (bit) : "cc");
  return rv;
#else
  const bitscan_t *cp;

  cp = (const bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  return (int)((*cp >> (bit & BITSCAN_MASK)) & BITSCAN_1);
#endif
}

static inline void set_bit(void *ptr, int bit)
{
#if defined(__GNUC__) && defined(__i386__)
  asm volatile("btsl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
  bitscan_t *cp;

  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  *cp |= (BITSCAN_1 << (bit & BITSCAN_MASK));
#endif
}

static inline void clr_bit(void *ptr, int bit)
{
#if defined(__GNUC__) && defined(__i386__)
  asm volatile("btcl %1,%0" : "=m" (*(bitscan_t *)ptr) : "r" (bit) : "cc");
#else
  bitscan_t *cp;

  cp = (bitscan_t *)ptr + (bit >> BITSCAN_SHIFT);
  *cp &= ~(BITSCAN_1 << (bit & BITSCAN_MASK));
#endif
}

/* Finds a one bit somewhere between [start, start+count) bit indicies.
   Returns the index, or "err" if no such bit is found. */
static int find_set_bit(const void *ptr, int start, int count, int err)
{
  const bitscan_t *cp, *ecp;
  bitscan_t mask, val;
  int i, end;

  end = start+count-1;

  cp = (bitscan_t *)ptr + (start >> BITSCAN_SHIFT);

  if ( ((start^end) & ~BITSCAN_MASK) == 0 ) {
    /* All falls within a single bitscan_t quantum */
    mask = BITSCAN_1 << (start & BITSCAN_MASK);
    val = *cp;
    for ( i = start ; i <= end ; i++ ) {
      if ( val & mask )
	return i;
      mask <<= 1;
    }
    return err;
  }
  
  mask = ~BITSCAN_0 << (start & BITSCAN_MASK);
  val = *cp++;
  if ( val & mask ) {
    end = start | BITSCAN_MASK;
    mask = BITSCAN_1 << (start & BITSCAN_MASK);
    for ( i = start ; i <= end ; i++ ) {
      if ( val & mask )
	return i;
      mask <<= 1;
    }
    assert(0);			/* Internal error */
  }

  ecp = (bitscan_t *)ptr + (end >> BITSCAN_SHIFT);
  start = (start & ~BITSCAN_MASK) + BITSCAN_BITS;

  while ( cp < ecp ) {
    val = *cp++;
    if ( val ) {
      mask = BITSCAN_1;
      end = start | BITSCAN_MASK;
      for ( i = start ; i <= end ; i++ ) {
	if ( val & mask )
	  return i;
	mask <<= 1;
      }
      assert(0);		/* Internal error */
    }
    start += BITSCAN_BITS;
  }

  /* Scan final word */
  val = *cp;
  mask = BITSCAN_1;
  for ( i = start ; i <= end ; i++ ) {
    if ( val & mask )
      return i;
    mask <<= 1;
  }
  return err;			/* Nothing found */
}

static struct ObjStore *os;
static struct arena_header *ah;
    
/*
 * Initalize the object store arena allocator.  This returns NULL
 * on failure, or a pointer to the "root data pointer" array if
 * successful.
 */
void **objstore_arena_init(const char *main_file, const char *log_file)
{
  size_t arena_len = sizeof(struct arena_header); /* Minimum initial size */

  if ( !objstore_init(main_file, log_file, &arena_len) )
    return NULL;		/* Failed to initialize arena */

  os = objstore_os_struct;
  ah = (struct arena_header *)os->arena;

  if ( memcmp(ah->arena_magic, objstore_arena_magic, 16) != 0 ) {
    if ( memcmp(ah->arena_magic, objstore_arena_zero, 16) == 0 ) {
      size_t total_size, bitmap_size;
      int i, header_pad;

      memset(ah, 0, sizeof(*ah)); /* Just in case */

      /* Uninitialized arena */
      memcpy(ah->arena_magic, objstore_arena_magic, 16);
      ah->arena_byteorder = 0x12345678;
      ah->arena_bytesize  = CHAR_BIT;
      ah->arena_ptrsize   = sizeof(void *);
      ah->arena_base      = (void *)ah;
      ah->buddy_order_min = BUDDY_ORDER_MIN;

      /* Header size must be padded to a multiple of BUDDY_SIZE_MIN
	 as well as the hardware page size; this better be a power of 2! */
      header_pad = (os->pagesize > BUDDY_SIZE_MIN)
	? os->pagesize : BUDDY_SIZE_MIN;
      assert((header_pad & (header_pad-1)) == 0);
      ah->header_size = (sizeof(struct arena_header) + header_pad - 1)
	& ~(header_pad-1);

      ah->data_start      = (char *)ah + ah->header_size;
      ah->arena_size_lg2  = ARENA_START_SIZE_LG2;
      bitmap_size =  1UL << (ARENA_START_SIZE_LG2-BUDDY_ORDER_MIN-1);
      total_size = ah->header_size + ARENA_START_SIZE + (bitmap_size << 1);
      ah->free_bitmap  = (char *)ah->data_start + ARENA_START_SIZE;
      ah->alloc_bitmap = (char *)ah->free_bitmap + bitmap_size;

      if ( objstore_extend(total_size) < 0 )
	return NULL;		/* Failed to establish initial arena */

      /* Compute SLAB definitions */
      for ( i = 0 ; slabsizes[i] ; i++ ) {
	int header_size = sizeof(struct slab_header);
	int bytes = BUDDY_SIZE_MIN - header_size;
	int size = slabsizes[i];
	int count = bytes/size;
	int data_offset;

	while ( 1 ) {
	  /* Compute header+bitmap size in bytes; rounded up to MINIMUM_ALIGN */
	  data_offset = header_size + ((count+7) >> 3);
	  data_offset = ((data_offset+MINIMUM_ALIGN-1) & ~MINIMUM_ALIGN_MASK);
	  if ( data_offset+count*size <= BUDDY_SIZE_MIN )
	    break;

	  count--;
	}
	ah->slab[i].size = size;
	ah->slab[i].count = count;
	ah->slab[i].data_offset = data_offset;
      }

      /* The bitmasks contains zeroes already; set the free bit on the topmost order. */
      set_bit(ah->free_bitmap, 1);
    }
  }

  if ( memcmp(ah->arena_magic, objstore_arena_magic, 16) != 0 ||
       ah->arena_byteorder != 0x12345678 ||
       ah->arena_bytesize  != CHAR_BIT   ||
       ah->arena_ptrsize   != sizeof(void *) ||
       ah->arena_base      != (void *)ah ||
       ah->buddy_order_min != BUDDY_ORDER_MIN ) {
    return NULL;		/* Incompatible or corrupt arena */
  }

  return ah->root_data_ptrs;
}

/*
 * This function expands a bitmap from oorder orders to norder orders.
 * This will not operate properly on a bitmap (old or new) that covers
 * less than 3 orders.  This assumes that the nbitmap area is already
 * initalized to zero.
 *
 * Note that "orders" here refers to orders of bitmap, which is usually
 * arena_size_lg2 - BUDDY_ORDER_MIN + 1.
 */
static void objstore_expand_bitmap(void *nbitmap, const void *obitmap, int norder, int oorder)
{
  int deltao, o, i, obit, nbit;
  int obyte, nbyte;

  assert(norder > oorder);
  deltao = norder - oorder;

  /* First, expand the orders which have fractional bytes */
  obit = 1;  nbit = 1 << deltao;
  for ( o = 0 ; o < 3 ; o++ ) {
    for ( i = 0 ; i < obit ; i++ ) {
      if ( test_bit(obitmap, obit+i) )
	set_bit(nbitmap, nbit+i);
    }
    obit <<= 1;  nbit <<= 1;
  }

  /* Then expand the orders which have complete bytes */
  obyte = 1;  nbyte = 1 << deltao;
  for ( o = 3 ; o < oorder ; o++ ) {
    memcpy((unsigned char *)nbitmap + nbyte,
	   (unsigned char *)obitmap + obyte,
	   obyte);
    obyte <<= 1;  nbyte <<= 1;
  }
}

/*
 * This function expands the arena to the specified log size.
 */
static int objstore_extend_arena(int logsize)
{
  size_t new_arena_size = (size_t)1 << logsize;
  size_t total_size;
  int ologsize = ah->arena_size_lg2;
  int bitmap_size;
  void *newfreemap, *newallocmap;
  int obp;

  assert(logsize > ologsize);

  DPRINTF(("arena: extending arena to order %d: ", logsize));

  bitmap_size =  1 << (logsize-BUDDY_ORDER_MIN-1);
  total_size = ah->header_size + new_arena_size + (bitmap_size << 1);
  newfreemap  = (char *)ah->data_start + new_arena_size;
  newallocmap = (char *)newfreemap + bitmap_size;
  
  if ( objstore_extend(total_size) < 0 ) {
    DPRINTF(("failed\n"));
    return -1;			/* Extension failed */
  }

  /* Otherwise, we just extended the area; reconstruct the bitmaps */
  objstore_expand_bitmap(newfreemap, ah->free_bitmap,
			 logsize-BUDDY_ORDER_MIN+1, ologsize-BUDDY_ORDER_MIN+1);
  objstore_expand_bitmap(newallocmap, ah->alloc_bitmap,
			 logsize-BUDDY_ORDER_MIN+1, ologsize-BUDDY_ORDER_MIN+1);
  ah->free_bitmap    = newfreemap;
  ah->alloc_bitmap   = newallocmap;
  ah->arena_size_lg2 = logsize;

  /* Mark the new allocations available */
  obp = 1 << (logsize-ologsize);
  if ( test_bit(newfreemap, obp) ) {
    /* The arena is completely unallocated... */
    clr_bit(newfreemap, obp);
    set_bit(newfreemap, 1);
  } else {
    /* March up the hierarchy and set the new buddies to available */
    while ( obp > 1 ) {
      set_bit(newfreemap, obp^1);
      obp >>= 1;
    }
  }

  DPRINTF(("succeeded.\n"));
  DPRINTF(("arena: new bitmaps start at %p\n", newfreemap));
  return 0;
}

/*
 * This function finds a free buddy-system allocation of the specified rorder,
 * and returns its xbit value.  It does mark it unavailable in the free bitmap,
 * but does not mark it as an "allocation" in the allocation bitmap (the latter
 * is used to determine what size free() we need to do.
 */
static int objstore_find_free_chunk(int rorder)
{
  int obit, xbit;

  obit = 1 << rorder;
  xbit = find_set_bit(ah->free_bitmap, obit, obit, 0);

  if ( !xbit ) {
    if ( rorder == 0 )
      return 0;			/* We're out */
    xbit = objstore_find_free_chunk(rorder-1);
    if ( !xbit )
      return 0;			/* All out of those, sir */
    DPRINTF(("buddy: splitting rorder %2d %8d -> %d %d\n", rorder-1, xbit, xbit << 1, (xbit << 1)+1));
    xbit <<= 1;			/* Convert to address of fragments */
    set_bit(ah->free_bitmap, xbit+1); /* Upper buddy is available */
    /* Return the lower buddy */
  } else {
    clr_bit(ah->free_bitmap, xbit); /* No longer available */
  }
  DPRINTF(("buddy: allocated rorder %2d %8d\n", rorder, xbit));
  return xbit;
}

static void *objstore_malloc_buddy(size_t size)
{
  int order = BUDDY_ORDER_MIN;
  int rorder;
  int xbit, obit;
  void *p;

  while ( size > ((size_t)1 << order) )
    order++;

  /* Now we know the order */
  if ( order > ah->arena_size_lg2 ) {
    if ( objstore_extend_arena(order+1) )
      return NULL;		/* Unable to extend arena */
  }

  /* Convert to order relative to the arena size order */
  do {
    rorder = ah->arena_size_lg2 - order;
    obit = 1 << rorder;

    DPRINTF(("buddy: trying to allocate %d bytes, rorder = %d\n", size, rorder));

    xbit = objstore_find_free_chunk(rorder);
    if ( !xbit ) {
      /* Need to extend */
      if ( objstore_extend_arena(ah->arena_size_lg2 + 1) )
	return NULL;		/* Failed to extend */
    }
  } while ( !xbit );

  /* Mark this as a proper allocation (used to find the size on free()) */
  set_bit(ah->alloc_bitmap, xbit);

  p = (void *)((char *)ah->data_start + ((uintptr_t)(xbit-obit) << order));

  DPRINTF(("buddy: allocated %u/%u bytes at %p\n", size, 1U << order, p));
  return p;
}

static struct slab_header *objstore_make_new_slab(struct slab_info *si, int index)
{
  struct slab_header *sh;
  unsigned char *slab_bitmap;
  int bitmap_all_set_bytes = si->count >> 3;
  int bitmap_bits_left = si->count & 7;

  /* Get a page from the buddy system allocator */
  sh = objstore_malloc_buddy(BUDDY_SIZE_MIN);
  if ( !sh )
    return NULL;

  DPRINTF(("slab:  allocating new page for size %d at %p\n", si->size, sh));
  assert(index == si - &ah->slab[0]);

  sh->magic       = SLAB_MAGIC;
  sh->free_count  = si->count;
  sh->index       = index;
  sh->next        = si->list;
  sh->rev         = &(si->list);

  slab_bitmap = (unsigned char *)(sh+1);
  
  /* Mark all SLABs as available */
  memset(slab_bitmap, ~0, bitmap_all_set_bytes);
  slab_bitmap[bitmap_all_set_bytes] = (1 << bitmap_bits_left)-1;
  
  if ( sh->next ) {
    sh->next->rev = &(sh->next);
    assert(sh->next->index == index);
  }

  return (si->list = sh);
}

static void *objstore_malloc_slab(size_t size)
{
  int i, index;
  int which;
  struct slab_info *si;
  struct slab_header *sh;
  void *slab_bitmap;
  void *p;

  /* POSIX sayeth: thou shalt return unique addresses for malloc(0); */
  if ( size == 0 ) size = 1;

  index = 0;
  si = &ah->slab[0];
  for ( i = 1 ; i < SLAB_INFO_COUNT ; i++ ) {
    if ( size <= si[1].size ) {
      si++;
      index++;
    } else
      break;
  }

  /* Now si points to the slab_info header we want to allocate from */
  DPRINTF(("slab:  trying to allocate %d bytes, slab size %d bytes\n",
	   size, si->size));

  sh = si->list;
  if ( !sh ) {
    /* Empty free list, need a new page */
    if ( !(sh = objstore_make_new_slab(si,index)) )
      return NULL;		/* Unavailable to allocate new slab */
  }

  /* It *better* be the same kind of slab... */
  assert(sh->magic == SLAB_MAGIC);
  assert(sh->index == index);
  
  slab_bitmap = (unsigned char *)(sh+1);
  
  which = find_set_bit(slab_bitmap, 0, si->count, -1);
  assert(which >= 0);		/* Otherwise something is bad... */

  clr_bit(slab_bitmap, which);	/* No longer available */

  if ( --(sh->free_count) == 0 ) {
    /* We just allocated the last slab, take off the free list */
    si->list = sh->next;
    if ( sh->next ) {
      sh->next->rev = &(si->list);
      assert(sh->next->index == sh->index);
    }
  }
  
  p = (void *)((char *)sh + si->data_offset + which*si->size);
  DPRINTF(("slab:  allocated %d/%d bytes at %p, %d/%d slabs in use\n",
	   size, si->size, p, si->count-sh->free_count, si->count));
  return p;
}

void *objstore_malloc(size_t size)
{
  if ( size > ah->slab[0].size )
    return objstore_malloc_buddy(size);
  else
    return objstore_malloc_slab(size);
}

static void objstore_free_chunk(int xbit, int rorder)
{
  if ( rorder > 0 ) {
    int bxbit = xbit^1;		/* Buddy xbit */
    if ( test_bit(ah->free_bitmap, bxbit) ) {
      /* Buddy is free. */
      clr_bit(ah->free_bitmap, bxbit);
      DPRINTF(("buddy: coalescing rorder %2d %d %d -> %2d %d\n",
	       rorder, xbit, bxbit, rorder-1, (xbit >> 1)));
      objstore_free_chunk((xbit >> 1), rorder-1);
      return;
    }
  }
  set_bit(ah->free_bitmap, xbit);
}

/*
 * This routine finds the parameters for one particular
 * buddy allocation from its address; used by free() and
 * realloc().
 */
struct buddy_params {
  int xbit;
  int rorder;
};
static struct buddy_params objstore_find_alloc_buddy(void *ptr)
{
  struct buddy_params bp;
  uintptr_t offset = (uintptr_t)ptr - (uintptr_t)ah->data_start;
  int order, rorder;
  int xbit, obit;

  assert(offset < (1UL << ah->arena_size_lg2)); /* Not inside the arena?? */

  for ( rorder = 0, order = ah->arena_size_lg2 ;
	order >= BUDDY_ORDER_MIN ;
	rorder++, order-- ) {
    if ( offset & ((1UL << order)-1) )
      continue;			/* Can't be this order */

    obit = 1 << rorder;
    xbit = obit + (offset >> order);
    
    if ( test_bit(ah->alloc_bitmap, xbit) ) {
      /* We're this order... */
      bp.xbit = xbit;  bp.rorder = rorder;
      return bp;
    }
  }

  abort();			/* Freeing bogus memory? */
}
  
static void objstore_free_buddy(void *ptr)
{
  struct buddy_params bp;

  DPRINTF(("buddy: freeing allocation at %p\n", ptr));
  bp = objstore_find_alloc_buddy(ptr);
  DPRINTF(("buddy: freeing rorder %2d %8d\n", bp.rorder, bp.xbit));
  clr_bit(ah->alloc_bitmap, bp.xbit);
  objstore_free_chunk(bp.xbit, bp.rorder);
}

static void objstore_free_slab(void *ptr)
{
  struct slab_header *sh;
  struct slab_info   *si;
  int offset, which, free_count;
  unsigned char *slab_bitmap;

  /* 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];
  slab_bitmap = (unsigned char *)sh +
    ((sizeof(struct slab_header)+MINIMUM_ALIGN-1) & ~MINIMUM_ALIGN_MASK);

  DPRINTF(("slab:  Freeing size %d slab at %p, %d/%d allocated\n",
	   si->size, ptr, si->count-sh->free_count, si->count));

  offset = ((uintptr_t)ptr & (BUDDY_SIZE_MIN-1)) - si->data_offset;
  assert(offset >= 0);
  which = offset/si->size;
  assert(offset == which*si->size);

  free_count = sh->free_count;

  if ( free_count == si->count-1 ) {
    /* Deallocated the entire page; give back to buddy system */
    DPRINTF(("slab:  Returning page %p back to the buddy system\n", sh));
    *(sh->rev) = sh->next;	/* Remove from free list */
    if ( sh->next ) {
      sh->next->rev = sh->rev;
      assert(sh->next->index == sh->index);
    }
#ifndef NDEBUG
    /* This unfortunately makes the page dirty */
    memset(sh, 0, BUDDY_SIZE_MIN);
#endif
    objstore_free_buddy(sh);
  } else {
    set_bit(slab_bitmap, which);
    sh->free_count = free_count+1;
    if ( free_count == 0 ) {
      /* Page is no longer full, add to free list */
      DPRINTF(("slab:  Adding page %p back onto free list for slab size %d\n",
	       sh, si->size));
      assert(sh->index == si - &ah->slab[0]);
      sh->rev  = &(si->list);
      sh->next = si->list;
      if ( sh->next ) {
	sh->next->rev = &(sh->next);
	assert(sh->next->index == sh->index);
      }
      si->list = sh;
    }
  }
}

void objstore_free(void *ptr)
{
  /* Buddy allocations are ALWAYS page-aligned, SLAB allocations never */
  if ( (uintptr_t)ptr & (BUDDY_SIZE_MIN-1) )
    objstore_free_slab(ptr);
  else
    objstore_free_buddy(ptr);
}

static void *objstore_realloc_buddy(void *ptr, size_t new_size)
{
  struct buddy_params bp;
  int order, rorder;
  int xbit, obit, i;
  void *nptr;
  
  bp = objstore_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... */
    if ( objstore_extend_arena(order+1) )
      return NULL;
  }

  rorder = ah->arena_size_lg2 - order;

  DPRINTF(("buddy: realloc rorder %d -> rorder %d\n",
	   bp.rorder, 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));
	nptr = objstore_malloc_buddy(new_size);
	if ( !nptr )
	  return NULL;		/* realloc failed */

	memcpy(nptr, ptr, current_size);
	
	/* Free the old area */
	DPRINTF(("buddy: freeing rorder %2d %8d\n", bp.rorder, bp.xbit));
	clr_bit(ah->alloc_bitmap, bp.xbit);
	objstore_free_chunk(bp.xbit, bp.rorder);

	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 *objstore_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 %d\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 = objstore_malloc(new_size);
    if ( !nptr )
      return NULL;
    memcpy(nptr, ptr, si->size);
    objstore_free_slab(ptr);
    return nptr;
  } else if ( new_size < (si->size >> 2) ) {
    void *nptr = objstore_malloc_slab(new_size);
    if ( !nptr )
      return ptr;		/* Old allocation still OK */
    memcpy(nptr, ptr, new_size);
    objstore_free_slab(ptr);
    return nptr;
  } else {
    /* Nothing to do... */
    return ptr;
  }
}

void *objstore_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 ( new_size == 0 ) {
    objstore_free(ptr);
    return NULL;
  } else if ( !ptr ) {
    return objstore_malloc(new_size);
  }

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

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