db2/common/db_salloc.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997, 1998
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7
   8 #include "config.h"
   9
  10 #ifndef lint
  11 static const char sccsid[] = "@(#)db_salloc.c   10.13 (Sleepycat) 5/10/98";
  12 #endif /* not lint */
  13
  14 #ifndef NO_SYSTEM_INCLUDES
  15 #include <sys/types.h>
  16
  17 #include <errno.h>
  18 #include <string.h>
  19 #endif
  20
  21 #include "db_int.h"
  22 #include "shqueue.h"
  23 #include "common_ext.h"
  24
  25 /*
  26  * Implement shared memory region allocation, using simple first-fit algorithm.
  27  * The model is that we take a "chunk" of shared memory store and begin carving
  28  * it up into areas, similarly to how malloc works.  We do coalescing on free.
  29  *
  30  * The "len" field in the __data struct contains the length of the free region
  31  * (less the size_t bytes that holds the length).  We use the address provided
  32  * by the caller to find this length, which allows us to free a chunk without
  33  * requiring that the caller pass in the length of the chunk they're freeing.
  34  */
  35 SH_LIST_HEAD(__head);
  36 struct __data {
  37         size_t len;
  38         SH_LIST_ENTRY links;
  39 };
  40
  41 /*
  42  * __db_shalloc_init --
  43  *      Initialize the area as one large chunk.
  44  *
  45  * PUBLIC: void __db_shalloc_init __P((void *, size_t));
  46  */
  47 void
  48 __db_shalloc_init(area, size)
  49         void *area;
  50         size_t size;
  51 {
  52         struct __data *elp;
  53         struct __head *hp;
  54
  55         hp = area;
  56         SH_LIST_INIT(hp);
  57
  58         elp = (struct __data *)(hp + 1);
  59         elp->len = size - sizeof(struct __head) - sizeof(elp->len);
  60         SH_LIST_INSERT_HEAD(hp, elp, links, __data);
  61 }
  62
  63 /*
  64  * __db_shalloc --
  65  *      Allocate some space from the shared region.
  66  *
  67  * PUBLIC: int __db_shalloc __P((void *, size_t, size_t, void *));
  68  */
  69 int
  70 __db_shalloc(p, len, align, retp)
  71         void *p, *retp;
  72         size_t len, align;
  73 {
  74         struct __data *elp;
  75         size_t *sp;
  76         void *rp;
  77
  78         /*
  79          * We never allocate less than the size of a struct __data, align
  80          * to less than a size_t boundary, or align to something that's not
  81          * a multiple of a size_t.
  82          */
  83         if (len < sizeof(struct __data))
  84                 len = sizeof(struct __data);
  85         align = align <= sizeof(size_t) ?
  86             sizeof(size_t) : ALIGN(align, sizeof(size_t));
  87
  88         /* Walk the list, looking for a slot. */
  89         for (elp = SH_LIST_FIRST((struct __head *)p, __data);
  90             elp != NULL;
  91             elp = SH_LIST_NEXT(elp, links, __data)) {
  92                 /*
  93                  * Calculate the value of the returned pointer if we were to
  94                  * use this chunk.
  95                  *      + Find the end of the chunk.
  96                  *      + Subtract the memory the user wants.
  97                  *      + Find the closest previous correctly-aligned address.
  98                  */
  99                 rp = (u_int8_t *)elp + sizeof(size_t) + elp->len;
 100                 rp = (u_int8_t *)rp - len;
 101                 rp = (u_int8_t *)((ALIGNTYPE)rp & ~(align - 1));
 102
 103                 /*
 104                  * Rp may now point before elp->links, in which case the chunk
 105                  * was too small, and we have to try again.
 106                  */
 107                 if ((u_int8_t *)rp < (u_int8_t *)&elp->links)
 108                         continue;
 109
 110                 *(void **)retp = rp;
 111
 112 #define SHALLOC_FRAGMENT        32
 113                 /*
 114                  * If there are at least SHALLOC_FRAGMENT additional bytes of
 115                  * memory, divide the chunk into two chunks.
 116                  */
 117                 if ((u_int8_t *)rp >=
 118                     (u_int8_t *)&elp->links + SHALLOC_FRAGMENT) {
 119                         sp = rp;
 120                         *--sp = elp->len -
 121                             ((u_int8_t *)rp - (u_int8_t *)&elp->links);
 122                         elp->len -= *sp + sizeof(size_t);
 123                         return (0);
 124                 }
 125
 126                 /*
 127                  * Otherwise, we return the entire chunk, wasting some amount
 128                  * of space to keep the list compact.  However, because the
 129                  * address we're returning to the user may not be the address
 130                  * of the start of the region for alignment reasons, set the
 131                  * size_t length fields back to the "real" length field to a
 132                  * flag value, so that we can find the real length during free.
 133                  */
 134 #define ILLEGAL_SIZE    1
 135                 SH_LIST_REMOVE(elp, links, __data);
 136                 for (sp = rp; (u_int8_t *)--sp >= (u_int8_t *)&elp->links;)
 137                         *sp = ILLEGAL_SIZE;
 138                 return (0);
 139         }
 140
 141         /* Nothing found large enough; need to grow the region. */
 142         return (ENOMEM);
 143 }
 144
 145 /*
 146  * __db_shalloc_free --
 147  *      Free a shared memory allocation.
 148  *
 149  * PUBLIC: void __db_shalloc_free __P((void *, void *));
 150  */
 151 void
 152 __db_shalloc_free(regionp, ptr)
 153         void *regionp, *ptr;
 154 {
 155         struct __data *elp, *lastp, *newp;
 156         struct __head *hp;
 157         size_t free_size, *sp;
 158         int merged;
 159
 160         /*
 161          * Step back over flagged length fields to find the beginning of
 162          * the object and its real size.
 163          */
 164         for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
 165                 ;
 166         ptr = sp;
 167
 168         newp = (struct __data *)((u_int8_t *)ptr - sizeof(size_t));
 169         free_size = newp->len;
 170
 171         /* Trash the returned memory. */
 172 #ifdef DIAGNOSTIC
 173         memset(ptr, 0xff, free_size);
 174 #endif
 175
 176         /*
 177          * Walk the list, looking for where this entry goes.
 178          *
 179          * We keep the free list sorted by address so that coalescing is
 180          * trivial.
 181          *
 182          * XXX
 183          * Probably worth profiling this to see how expensive it is.
 184          */
 185         hp = (struct __head *)regionp;
 186         for (elp = SH_LIST_FIRST(hp, __data), lastp = NULL;
 187             elp != NULL && (void *)elp < (void *)ptr;
 188             lastp = elp, elp = SH_LIST_NEXT(elp, links, __data))
 189                 ;
 190
 191         /*
 192          * Elp is either NULL (we reached the end of the list), or the slot
 193          * after the one that's being returned.  Lastp is either NULL (we're
 194          * returning the first element of the list) or the element before the
 195          * one being returned.
 196          *
 197          * Check for coalescing with the next element.
 198          */
 199         merged = 0;
 200         if ((u_int8_t *)ptr + free_size == (u_int8_t *)elp) {
 201                 newp->len += elp->len + sizeof(size_t);
 202                 SH_LIST_REMOVE(elp, links, __data);
 203                 if (lastp != NULL)
 204                         SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
 205                 else
 206                         SH_LIST_INSERT_HEAD(hp, newp, links, __data);
 207                 merged = 1;
 208         }
 209
 210         /* Check for coalescing with the previous element. */
 211         if (lastp != NULL && (u_int8_t *)lastp +
 212             lastp->len + sizeof(size_t) == (u_int8_t *)newp) {
 213                 lastp->len += newp->len + sizeof(size_t);
 214
 215                 /*
 216                  * If we have already put the new element into the list take
 217                  * it back off again because it's just been merged with the
 218                  * previous element.
 219                  */
 220                 if (merged)
 221                         SH_LIST_REMOVE(newp, links, __data);
 222                 merged = 1;
 223         }
 224
 225         if (!merged) {
 226                 if (lastp == NULL)
 227                         SH_LIST_INSERT_HEAD(hp, newp, links, __data);
 228                 else
 229                         SH_LIST_INSERT_AFTER(lastp, newp, links, __data);
 230         }
 231 }
 232
 233 /*
 234  * __db_shalloc_count --
 235  *      Return the amount of memory on the free list.
 236  *
 237  * PUBLIC: size_t __db_shalloc_count __P((void *));
 238  */
 239 size_t
 240 __db_shalloc_count(addr)
 241         void *addr;
 242 {
 243         struct __data *elp;
 244         size_t count;
 245
 246         count = 0;
 247         for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
 248             elp != NULL;
 249             elp = SH_LIST_NEXT(elp, links, __data))
 250                 count += elp->len;
 251
 252         return (count);
 253 }
 254
 255 /*
 256  * __db_shsizeof --
 257  *      Return the size of a shalloc'd piece of memory.
 258  *
 259  * PUBLIC: size_t __db_shsizeof __P((void *));
 260  */
 261 size_t
 262 __db_shsizeof(ptr)
 263         void *ptr;
 264 {
 265         struct __data *elp;
 266         size_t *sp;
 267
 268         /*
 269          * Step back over flagged length fields to find the beginning of
 270          * the object and its real size.
 271          */
 272         for (sp = (size_t *)ptr; sp[-1] == ILLEGAL_SIZE; --sp)
 273                 ;
 274
 275         elp = (struct __data *)((u_int8_t *)sp - sizeof(size_t));
 276         return (elp->len);
 277 }
 278
 279 /*
 280  * __db_shalloc_dump --
 281  *
 282  * PUBLIC: void __db_shalloc_dump __P((void *, FILE *));
 283  */
 284 void
 285 __db_shalloc_dump(addr, fp)
 286         void *addr;
 287         FILE *fp;
 288 {
 289         struct __data *elp;
 290
 291         /* Make it easy to call from the debugger. */
 292         if (fp == NULL)
 293                 fp = stderr;
 294
 295         fprintf(fp, "%s\nMemory free list\n", DB_LINE);
 296
 297         for (elp = SH_LIST_FIRST((struct __head *)addr, __data);
 298             elp != NULL;
 299             elp = SH_LIST_NEXT(elp, links, __data))
 300                 fprintf(fp, "%#lx: %lu\t", (u_long)elp, (u_long)elp->len);
 301         fprintf(fp, "\n");
 302 }