firmware/buflib.c

   1 /***************************************************************************
   2 *             __________               __   ___.
   3 *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4 *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5 *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6 *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7 *                     \/            \/     \/    \/            \/
   8 * $Id$
   9 *
  10 * This is a memory allocator designed to provide reasonable management of free
  11 * space and fast access to allocated data. More than one allocator can be used
  12 * at a time by initializing multiple contexts.
  13 *
  14 * Copyright (C) 2009 Andrew Mahone
  15 * Copyright (C) 2011 Thomas Martitz
  16 *
  17 *
  18 * This program is free software; you can redistribute it and/or
  19 * modify it under the terms of the GNU General Public License
  20 * as published by the Free Software Foundation; either version 2
  21 * of the License, or (at your option) any later version.
  22 *
  23 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  24 * KIND, either express or implied.
  25 *
  26 ****************************************************************************/
  27
  28 #include <stdlib.h> /* for abs() */
  29 #include <stdio.h> /* for snprintf() */
  30 #include "buflib.h"
  31 #include "string-extra.h" /* strlcpy() */
  32 #include "debug.h"
  33 #include "buffer.h"
  34 #include "system.h" /* for ALIGN_*() */
  35
  36 /* The main goal of this design is fast fetching of the pointer for a handle.
  37  * For that reason, the handles are stored in a table at the end of the buffer
  38  * with a fixed address, so that returning the pointer for a handle is a simple
  39  * table lookup. To reduce the frequency with which allocated blocks will need
  40  * to be moved to free space, allocations grow up in address from the start of
  41  * the buffer. The buffer is treated as an array of union buflib_data. Blocks
  42  * start with a length marker, which is included in their length. Free blocks
  43  * are marked by negative length. Allocated blocks have a positiv length marker,
  44  * and additional metadata forllowing that: It follows a pointer
  45  * (union buflib_data*) to the corresponding handle table entry. so that it can
  46  * be quickly found and updated during compaction. After that follows
  47  * the pointer to the struct buflib_callbacks associated with this allocation
  48  * (may be NULL). That pointer follows a variable length character array
  49  * containing the nul-terminated string identifier of the allocation. After this
  50  * array there's a length marker for the length of the character array including
  51  * this length marker (counted in n*sizeof(union buflib_data)), which allows
  52  * to find the start of the character array (and therefore the start of the
  53  * entire block) when only the handle or payload start is known.
  54  *
  55  * Example:
  56  * |<- alloc block #1 ->|<- unalloc block ->|<- alloc block #2      ->|<-handle table->|
  57  * |L|H|C|cccc|L2|XXXXXX|-L|YYYYYYYYYYYYYYYY|L|H|C|cc|L2|XXXXXXXXXXXXX|AAA|
  58  *
  59  * L - length marker (negative if block unallocated)
  60  * H - handle table enry pointer
  61  * C - pointer to struct buflib_callbacks
  62  * c - variable sized string identifier
  63  * L2 - second length marker for string identifier
  64  * X - actual payload
  65  * Y - unallocated space
  66  *
  67  * A - pointer to start of payload (first X) in the handle table (may be null)
  68  *
  69  * The blocks can be walked by jumping the abs() of the L length marker, i.e.
  70  * union buflib_data* L;
  71  * for(L = start; L < end; L += abs(L->val)) { .... }
  72  *
  73  *
  74  * The allocator functions are passed a context struct so that two allocators
  75  * can be run, for example, one per core may be used, with convenience wrappers
  76  * for the single-allocator case that use a predefined context.
  77  */
  78
  79 #define B_ALIGN_DOWN(x) \
  80     ALIGN_DOWN(x, sizeof(union buflib_data))
  81
  82 #define B_ALIGN_UP(x) \
  83     ALIGN_UP(x, sizeof(union buflib_data))
  84
  85 #ifdef DEBUG
  86     #include <stdio.h>
  87     #define BDEBUGF DEBUGF
  88 #else
  89     #define BDEBUGF(...) do { } while(0)
  90 #endif
  91
  92 static union buflib_data* find_first_free(struct buflib_context *ctx);
  93 static union buflib_data* find_block_before(struct buflib_context *ctx,
  94                                             union buflib_data* block,
  95                                             bool is_free);
  96 /* Initialize buffer manager */
  97 void
  98 buflib_init(struct buflib_context *ctx, void *buf, size_t size)
  99 {
 100     union buflib_data *bd_buf = buf;
 101
 102     /* Align on sizeof(buflib_data), to prevent unaligned access */
 103     ALIGN_BUFFER(bd_buf, size, sizeof(union buflib_data));
 104     size /= sizeof(union buflib_data);
 105     /* The handle table is initialized with no entries */
 106     ctx->handle_table = bd_buf + size;
 107     ctx->last_handle = bd_buf + size;
 108     ctx->first_free_handle = bd_buf + size - 1;
 109     ctx->buf_start = bd_buf;
 110     /* A marker is needed for the end of allocated data, to make sure that it
 111      * does not collide with the handle table, and to detect end-of-buffer.
 112      */
 113     ctx->alloc_end = bd_buf;
 114     ctx->compact = true;
 115
 116     BDEBUGF("buflib initialized with %d.%2d kiB", size / 1024, (size%1000)/10);
 117 }
 118
 119 /* Allocate a new handle, returning 0 on failure */
 120 static inline
 121 union buflib_data* handle_alloc(struct buflib_context *ctx)
 122 {
 123     union buflib_data *handle;
 124     /* first_free_handle is a lower bound on free handles, work through the
 125      * table from there until a handle containing NULL is found, or the end
 126      * of the table is reached.
 127      */
 128     for (handle = ctx->first_free_handle; handle >= ctx->last_handle; handle--)
 129         if (!handle->alloc)
 130             break;
 131     /* If the search went past the end of the table, it means we need to extend
 132      * the table to get a new handle.
 133      */
 134     if (handle < ctx->last_handle)
 135     {
 136         if (handle >= ctx->alloc_end)
 137             ctx->last_handle--;
 138         else
 139             return NULL;
 140     }
 141     handle->val = -1;
 142     return handle;
 143 }
 144
 145 /* Free one handle, shrinking the handle table if it's the last one */
 146 static inline
 147 void handle_free(struct buflib_context *ctx, union buflib_data *handle)
 148 {
 149     handle->alloc = 0;
 150     /* Update free handle lower bound if this handle has a lower index than the
 151      * old one.
 152      */
 153     if (handle > ctx->first_free_handle)
 154         ctx->first_free_handle = handle;
 155     if (handle == ctx->last_handle)
 156         ctx->last_handle++;
 157     else
 158         ctx->compact = false;
 159 }
 160
 161 /* Get the start block of an allocation */
 162 static union buflib_data* handle_to_block(struct buflib_context* ctx, int handle)
 163 {
 164     union buflib_data* name_field =
 165                 (union buflib_data*)buflib_get_name(ctx, handle);
 166
 167     return name_field - 3;
 168 }
 169
 170 /* Shrink the handle table, returning true if its size was reduced, false if
 171  * not
 172  */
 173 static inline
 174 bool
 175 handle_table_shrink(struct buflib_context *ctx)
 176 {
 177     bool rv;
 178     union buflib_data *handle;
 179     for (handle = ctx->last_handle; !(handle->alloc); handle++);
 180     if (handle > ctx->first_free_handle)
 181         ctx->first_free_handle = handle - 1;
 182     rv = handle != ctx->last_handle;
 183     ctx->last_handle = handle;
 184     return rv;
 185 }
 186
 187
 188 /* If shift is non-zero, it represents the number of places to move
 189  * blocks in memory. Calculate the new address for this block,
 190  * update its entry in the handle table, and then move its contents.
 191  *
 192  * Returns false if moving was unsucessful
 193  * (NULL callback or BUFLIB_CB_CANNOT_MOVE was returned)
 194  */
 195 static bool
 196 move_block(struct buflib_context* ctx, union buflib_data* block, int shift)
 197 {
 198     char* new_start;
 199     union buflib_data *new_block, *tmp = block[1].handle;
 200     struct buflib_callbacks *ops = block[2].ops;
 201     if (ops && !ops->move_callback)
 202         return false;
 203
 204     int handle = ctx->handle_table - tmp;
 205     BDEBUGF("%s(): moving \"%s\"(id=%d) by %d(%d)\n", __func__, block[3].name,
 206             handle, shift, shift*sizeof(union buflib_data));
 207     new_block = block + shift;
 208     new_start = tmp->alloc + shift*sizeof(union buflib_data);
 209     /* call the callback before moving */
 210     if (ops)
 211     {
 212         if (ops->move_callback(handle, tmp->alloc, new_start)
 213                 == BUFLIB_CB_CANNOT_MOVE)
 214             return false;
 215     }
 216     tmp->alloc = new_start; /* update handle table */
 217     memmove(new_block, block, block->val * sizeof(union buflib_data));
 218
 219     return true;
 220 }
 221
 222 /* Compact allocations and handle table, adjusting handle pointers as needed.
 223  * Return true if any space was freed or consolidated, false otherwise.
 224  */
 225 static bool
 226 buflib_compact(struct buflib_context *ctx)
 227 {
 228     BDEBUGF("%s(): Compacting!\n", __func__);
 229     union buflib_data *block,
 230                       *first_free = find_first_free(ctx);
 231     int shift = 0, len;
 232     /* Store the results of attempting to shrink the handle table */
 233     bool ret = handle_table_shrink(ctx);
 234     for(block = first_free; block < ctx->alloc_end; block += len)
 235     {
 236         len = block->val;
 237         /* This block is free, add its length to the shift value */
 238         if (len < 0)
 239         {
 240             shift += len;
 241             len = -len;
 242             continue;
 243         }
 244         /* attempt to fill any hole */
 245         if (-first_free->val >= block->val)
 246         {
 247             intptr_t size = -first_free->val;
 248             union buflib_data* next_block = block + block->val;
 249             if (move_block(ctx, block, first_free - block))
 250             {
 251                 /* moving was successful. Move alloc_end down if necessary */
 252                 if (ctx->alloc_end == next_block)
 253                     ctx->alloc_end = block;
 254                 /* Mark the block behind the just moved as free
 255                  * be careful to not overwrite an existing block */
 256                 if (size != block->val)
 257                 {
 258                     first_free += block->val;
 259                     first_free->val = block->val - size; /* negative */
 260                 }
 261                 continue;
 262             }
 263         }
 264         /* attempt move the allocation by shift */
 265         if (shift)
 266         {
 267             /* failing to move creates a hole,
 268              * therefore mark this block as not allocated */
 269             union buflib_data* target_block = block + shift;
 270             if (!move_block(ctx, block, shift))
 271             {
 272                 target_block->val = shift; /* this is a hole */
 273                 shift = 0;
 274             }
 275             else
 276             {   /* need to update the next free block, since the above hole
 277                  * handling might make shift 0 before alloc_end is reached */
 278                 union buflib_data* new_free = target_block + target_block->val;
 279                 new_free->val = shift;
 280             }
 281         }
 282     }
 283     /* Move the end-of-allocation mark, and return true if any new space has
 284      * been freed.
 285      */
 286     ctx->alloc_end += shift;
 287     ctx->compact = true;
 288     return ret || shift;
 289 }
 290
 291 /* Compact the buffer by trying both shrinking and moving.
 292  *
 293  * Try to move first. If unsuccesfull, try to shrink. If that was successful
 294  * try to move once more as there might be more room now.
 295  */
 296 static bool
 297 buflib_compact_and_shrink(struct buflib_context *ctx, unsigned shrink_hints)
 298 {
 299     bool result = false;
 300     /* if something compacted before already there will be no further gain */
 301     if (!ctx->compact)
 302         result = buflib_compact(ctx);
 303     if (!result)
 304     {
 305         union buflib_data* this;
 306         for(this = ctx->buf_start; this < ctx->alloc_end; this += abs(this->val))
 307         {
 308             if (this->val > 0 && this[2].ops
 309                               && this[2].ops->shrink_callback)
 310             {
 311                 int ret;
 312                 int handle = ctx->handle_table - this[1].handle;
 313                 char* data = this[1].handle->alloc;
 314                 bool last = (this+this->val) == ctx->alloc_end;
 315                 ret = this[2].ops->shrink_callback(handle, shrink_hints,
 316                                             data, (char*)(this+this->val)-data);
 317                 result |= (ret == BUFLIB_CB_OK);
 318                 /* this might have changed in the callback (if
 319                  * it shrinked from the top), get it again */
 320                 this = handle_to_block(ctx, handle);
 321                 /* could also change with shrinking from back */
 322                 if (last)
 323                     ctx->alloc_end = this + this->val;
 324             }
 325         }
 326         /* shrinking was successful at least once, try compaction again */
 327         if (result)
 328             result |= buflib_compact(ctx);
 329     }
 330
 331     return result;
 332 }
 333
 334 /* Shift buffered items by size units, and update handle pointers. The shift
 335  * value must be determined to be safe *before* calling.
 336  */
 337 static void
 338 buflib_buffer_shift(struct buflib_context *ctx, int shift)
 339 {
 340     memmove(ctx->buf_start + shift, ctx->buf_start,
 341         (ctx->alloc_end - ctx->buf_start) * sizeof(union buflib_data));
 342     union buflib_data *handle;
 343     for (handle = ctx->last_handle; handle < ctx->handle_table; handle++)
 344         if (handle->alloc)
 345             handle->alloc += shift;
 346     ctx->buf_start += shift;
 347     ctx->alloc_end += shift;
 348 }
 349
 350 /* Shift buffered items up by size bytes, or as many as possible if size == 0.
 351  * Set size to the number of bytes freed.
 352  */
 353 void*
 354 buflib_buffer_out(struct buflib_context *ctx, size_t *size)
 355 {
 356     if (!ctx->compact)
 357         buflib_compact(ctx);
 358     size_t avail = ctx->last_handle - ctx->alloc_end;
 359     size_t avail_b = avail * sizeof(union buflib_data);
 360     if (*size && *size < avail_b)
 361     {
 362         avail = (*size + sizeof(union buflib_data) - 1)
 363             / sizeof(union buflib_data);
 364         avail_b = avail * sizeof(union buflib_data);
 365     }
 366     *size = avail_b;
 367     void *ret = ctx->buf_start;
 368     buflib_buffer_shift(ctx, avail);
 369     return ret;
 370 }
 371
 372 /* Shift buffered items down by size bytes */
 373 void
 374 buflib_buffer_in(struct buflib_context *ctx, int size)
 375 {
 376     size /= sizeof(union buflib_data);
 377     buflib_buffer_shift(ctx, -size);
 378 }
 379
 380 /* Allocate a buffer of size bytes, returning a handle for it */
 381 int
 382 buflib_alloc(struct buflib_context *ctx, size_t size)
 383 {
 384     return buflib_alloc_ex(ctx, size, "<anonymous>", NULL);
 385 }
 386
 387 /* Allocate a buffer of size bytes, returning a handle for it.
 388  *
 389  * The additional name parameter gives the allocation a human-readable name,
 390  * the ops parameter points to caller-implemented callbacks for moving and
 391  * shrinking. NULL for default callbacks (which do nothing but don't
 392  * prevent moving or shrinking)
 393  */
 394
 395 int
 396 buflib_alloc_ex(struct buflib_context *ctx, size_t size, const char *name,
 397                 struct buflib_callbacks *ops)
 398 {
 399     union buflib_data *handle, *block;
 400     size_t name_len = name ? B_ALIGN_UP(strlen(name)+1) : 0;
 401     bool last;
 402     /* This really is assigned a value before use */
 403     int block_len;
 404     size += name_len;
 405     size = (size + sizeof(union buflib_data) - 1) /
 406            sizeof(union buflib_data)
 407            /* add 4 objects for alloc len, pointer to handle table entry and
 408             * name length, and the ops pointer */
 409            + 4;
 410 handle_alloc:
 411     handle = handle_alloc(ctx);
 412     if (!handle)
 413     {
 414         /* If allocation has failed, and compaction has succeded, it may be
 415          * possible to get a handle by trying again.
 416          */
 417         union buflib_data* last_block = find_block_before(ctx,
 418                                             ctx->alloc_end, false);
 419         struct buflib_callbacks* ops = last_block[2].ops;
 420         unsigned hints = 0;
 421         if (!ops || !ops->shrink_callback)
 422         {   /* the last one isn't shrinkable
 423              * make room in front of a shrinkable and move this alloc */
 424             hints = BUFLIB_SHRINK_POS_FRONT;
 425             hints |= last_block->val * sizeof(union buflib_data);
 426         }
 427         else if (ops && ops->shrink_callback)
 428         {   /* the last is shrinkable, make room for handles directly */
 429             hints = BUFLIB_SHRINK_POS_BACK;
 430             hints |= 16*sizeof(union buflib_data);
 431         }
 432         /* buflib_compact_and_shrink() will compact and move last_block()
 433          * if possible */
 434         if (buflib_compact_and_shrink(ctx, hints))
 435             goto handle_alloc;
 436         return -1;
 437     }
 438
 439 buffer_alloc:
 440     /* need to re-evaluate last before the loop because the last allocation
 441      * possibly made room in its front to fit this, so last would be wrong */
 442     last = false;
 443     for (block = find_first_free(ctx);;block += block_len)
 444     {
 445         /* If the last used block extends all the way to the handle table, the
 446          * block "after" it doesn't have a header. Because of this, it's easier
 447          * to always find the end of allocation by saving a pointer, and always
 448          * calculate the free space at the end by comparing it to the
 449          * last_handle pointer.
 450          */
 451         if(block == ctx->alloc_end)
 452         {
 453             last = true;
 454             block_len = ctx->last_handle - block;
 455             if ((size_t)block_len < size)
 456                 block = NULL;
 457             break;
 458         }
 459         block_len = block->val;
 460         /* blocks with positive length are already allocated. */
 461         if(block_len > 0)
 462             continue;
 463         block_len = -block_len;
 464         /* The search is first-fit, any fragmentation this causes will be
 465          * handled at compaction.
 466          */
 467         if ((size_t)block_len >= size)
 468             break;
 469     }
 470     if (!block)
 471     {
 472         /* Try compacting if allocation failed */
 473         unsigned hint = BUFLIB_SHRINK_POS_FRONT |
 474                     ((size*sizeof(union buflib_data))&BUFLIB_SHRINK_SIZE_MASK);
 475         if (buflib_compact_and_shrink(ctx, hint))
 476         {
 477             goto buffer_alloc;
 478         } else {
 479             handle->val=1;
 480             handle_free(ctx, handle);
 481             return -2;
 482         }
 483     }
 484
 485     /* Set up the allocated block, by marking the size allocated, and storing
 486      * a pointer to the handle.
 487      */
 488     union buflib_data *name_len_slot;
 489     block->val = size;
 490     block[1].handle = handle;
 491     block[2].ops = ops;
 492     strcpy(block[3].name, name);
 493     name_len_slot = (union buflib_data*)B_ALIGN_UP(block[3].name + name_len);
 494     name_len_slot->val = 1 + name_len/sizeof(union buflib_data);
 495     handle->alloc = (char*)(name_len_slot + 1);
 496
 497     block += size;
 498     /* alloc_end must be kept current if we're taking the last block. */
 499     if (last)
 500         ctx->alloc_end = block;
 501     /* Only free blocks *before* alloc_end have tagged length. */
 502     else if ((size_t)block_len > size)
 503         block->val = size - block_len;
 504     /* Return the handle index as a positive integer. */
 505     return ctx->handle_table - handle;
 506 }
 507
 508 static union buflib_data*
 509 find_first_free(struct buflib_context *ctx)
 510 {
 511     union buflib_data* ret = ctx->buf_start;
 512     while(ret < ctx->alloc_end)
 513     {
 514         if (ret->val < 0)
 515             break;
 516         ret += ret->val;
 517     }
 518     /* ret is now either a free block or the same as alloc_end, both is fine */
 519     return ret;
 520 }
 521
 522 /* Finds the free block before block, and returns NULL if it's not free */
 523 static union buflib_data*
 524 find_block_before(struct buflib_context *ctx, union buflib_data* block,
 525                   bool is_free)
 526 {
 527     union buflib_data *ret        = ctx->buf_start,
 528                       *next_block = ret;
 529
 530     /* find the block that's before the current one */
 531     while (next_block < block)
 532     {
 533         ret = next_block;
 534         next_block += abs(ret->val);
 535     }
 536
 537     /* If next_block == block, the above loop didn't go anywhere. If it did,
 538      * and the block before this one is empty, that is the wanted one
 539      */
 540     if (next_block == block && ret < block)
 541     {
 542         if (is_free && ret->val >= 0) /* NULL if found block isn't free */
 543             return NULL;
 544         return ret;
 545     }
 546     return NULL;
 547 }
 548
 549 /* Free the buffer associated with handle_num. */
 550 int
 551 buflib_free(struct buflib_context *ctx, int handle_num)
 552 {
 553     union buflib_data *handle = ctx->handle_table - handle_num,
 554                       *freed_block = handle_to_block(ctx, handle_num),
 555                       *block, *next_block;
 556     /* We need to find the block before the current one, to see if it is free
 557      * and can be merged with this one.
 558      */
 559     block = find_block_before(ctx, freed_block, true);
 560     if (block)
 561     {
 562         block->val -= freed_block->val;
 563     }
 564     else
 565     {
 566     /* Otherwise, set block to the newly-freed block, and mark it free, before
 567      * continuing on, since the code below exects block to point to a free
 568      * block which may have free space after it.
 569      */
 570         block = freed_block;
 571         block->val = -block->val;
 572     }
 573     next_block = block - block->val;
 574     /* Check if we are merging with the free space at alloc_end. */
 575     if (next_block == ctx->alloc_end)
 576         ctx->alloc_end = block;
 577     /* Otherwise, the next block might still be a "normal" free block, and the
 578      * mid-allocation free means that the buffer is no longer compact.
 579      */
 580     else {
 581         ctx->compact = false;
 582         if (next_block->val < 0)
 583             block->val += next_block->val;
 584     }
 585     handle_free(ctx, handle);
 586     handle->alloc = NULL;
 587
 588     return 0; /* unconditionally */
 589 }
 590
 591 /* Return the maximum allocatable memory in bytes */
 592 size_t
 593 buflib_available(struct buflib_context* ctx)
 594 {
 595     /* subtract 5 elements for
 596      * val, handle, name_len, ops and the handle table entry*/
 597     ptrdiff_t diff = (ctx->last_handle - ctx->alloc_end - 5);
 598     diff -= 16; /* space for future handles */
 599     diff *= sizeof(union buflib_data); /* make it bytes */
 600     diff -= 16; /* reserve 16 for the name */
 601
 602     if (diff > 0)
 603         return diff;
 604     else
 605         return 0;
 606 }
 607
 608 /*
 609  * Allocate all available (as returned by buflib_available()) memory and return
 610  * a handle to it
 611  *
 612  * This grabs a lock which can only be unlocked by buflib_free() or
 613  * buflib_shrink(), to protect from further allocations (which couldn't be
 614  * serviced anyway).
 615  */
 616 int
 617 buflib_alloc_maximum(struct buflib_context* ctx, const char* name, size_t *size, struct buflib_callbacks *ops)
 618 {
 619     /* limit name to 16 since that's what buflib_available() accounts for it */
 620     char buf[16];
 621     *size = buflib_available(ctx);
 622     strlcpy(buf, name, sizeof(buf));
 623
 624     return buflib_alloc_ex(ctx, *size, buf, ops);
 625 }
 626
 627 /* Shrink the allocation indicated by the handle according to new_start and
 628  * new_size. Grow is not possible, therefore new_start and new_start + new_size
 629  * must be within the original allocation
 630  */
 631 bool
 632 buflib_shrink(struct buflib_context* ctx, int handle, void* new_start, size_t new_size)
 633 {
 634     char* oldstart = buflib_get_data(ctx, handle);
 635     char* newstart = new_start;
 636     char* newend = newstart + new_size;
 637
 638     /* newstart must be higher and new_size not "negative" */
 639     if (newstart < oldstart || newend < newstart)
 640         return false;
 641     union buflib_data *block = handle_to_block(ctx, handle),
 642                       *old_next_block = block + block->val,
 643                 /* newstart isn't necessarily properly aligned but it
 644                  * needn't be since it's only dereferenced by the user code */
 645                       *aligned_newstart = (union buflib_data*)B_ALIGN_DOWN(newstart),
 646                       *aligned_oldstart = (union buflib_data*)B_ALIGN_DOWN(oldstart),
 647                       *new_next_block =   (union buflib_data*)B_ALIGN_UP(newend),
 648                       *new_block, metadata_size;
 649
 650     /* growing is not supported */
 651     if (new_next_block > old_next_block)
 652         return false;
 653
 654     metadata_size.val = aligned_oldstart - block;
 655     /* update val and the handle table entry */
 656     new_block = aligned_newstart - metadata_size.val;
 657     block[0].val = new_next_block - new_block;
 658
 659     block[1].handle->alloc = newstart;
 660     if (block != new_block)
 661     {
 662         /* move metadata over, i.e. pointer to handle table entry and name
 663          * This is actually the point of no return. Data in the allocation is
 664          * being modified, and therefore we must successfully finish the shrink
 665          * operation */
 666         memmove(new_block, block, metadata_size.val*sizeof(metadata_size));
 667         /* mark the old block unallocated */
 668         block->val = block - new_block;
 669         /* find the block before in order to merge with the new free space */
 670         union buflib_data *free_before = find_block_before(ctx, block, true);
 671         if (free_before)
 672             free_before->val += block->val;
 673
 674         /* We didn't handle size changes yet, assign block to the new one
 675          * the code below the wants block whether it changed or not */
 676         block = new_block;
 677     }
 678
 679     /* Now deal with size changes that create free blocks after the allocation */
 680     if (old_next_block != new_next_block)
 681     {
 682         if (ctx->alloc_end == old_next_block)
 683             ctx->alloc_end = new_next_block;
 684         else if (old_next_block->val < 0)
 685         {   /* enlarge next block by moving it up */
 686             new_next_block->val = old_next_block->val - (old_next_block - new_next_block);
 687         }
 688         else if (old_next_block != new_next_block)
 689         {   /* creating a hole */
 690             /* must be negative to indicate being unallocated */
 691             new_next_block->val = new_next_block - old_next_block;
 692         }
 693     }
 694
 695     return true;
 696 }
 697
 698 const char* buflib_get_name(struct buflib_context *ctx, int handle)
 699 {
 700     union buflib_data *data = ALIGN_DOWN(buflib_get_data(ctx, handle), sizeof (*data));
 701     size_t len = data[-1].val;
 702     if (len <= 1)
 703         return NULL;
 704     return data[-len].name;
 705 }
 706
 707 #ifdef BUFLIB_DEBUG_BLOCKS
 708 void buflib_print_allocs(struct buflib_context *ctx,
 709                                         void (*print)(int, const char*))
 710 {
 711     union buflib_data *this, *end = ctx->handle_table;
 712     char buf[128];
 713     for(this = end - 1; this >= ctx->last_handle; this--)
 714     {
 715         if (!this->alloc) continue;
 716
 717         int handle_num;
 718         const char *name;
 719         union buflib_data *block_start, *alloc_start;
 720         intptr_t alloc_len;
 721
 722         handle_num = end - this;
 723         alloc_start = buflib_get_data(ctx, handle_num);
 724         name = buflib_get_name(ctx, handle_num);
 725         block_start = (union buflib_data*)name - 3;
 726         alloc_len = block_start->val * sizeof(union buflib_data);
 727
 728         snprintf(buf, sizeof(buf),
 729                 "%s(%d):\t%p\n"
 730                 "   \t%p\n"
 731                 "   \t%ld\n",
 732                 name?:"(null)", handle_num, block_start, alloc_start, alloc_len);
 733         /* handle_num is 1-based */
 734         print(handle_num - 1, buf);
 735     }
 736 }
 737
 738 void buflib_print_blocks(struct buflib_context *ctx,
 739                                         void (*print)(int, const char*))
 740 {
 741     char buf[128];
 742     int i = 0;
 743     for(union buflib_data* this = ctx->buf_start;
 744                            this < ctx->alloc_end;
 745                            this += abs(this->val))
 746     {
 747         snprintf(buf, sizeof(buf), "%8p: val: %4ld (%s)",
 748                                 this, this->val,
 749                                 this->val > 0? this[3].name:"<unallocated>");
 750         print(i++, buf);
 751     }
 752 }
 753 #endif
 754
 755 #ifdef BUFLIB_DEBUG_BLOCK_SINGLE
 756 int buflib_get_num_blocks(struct buflib_context *ctx)
 757 {
 758     int i = 0;
 759     for(union buflib_data* this = ctx->buf_start;
 760                            this < ctx->alloc_end;
 761                            this += abs(this->val))
 762     {
 763         i++;
 764     }
 765     return i;
 766 }
 767
 768 void buflib_print_block_at(struct buflib_context *ctx, int block_num,
 769                                 char* buf, size_t bufsize)
 770 {
 771     union buflib_data* this = ctx->buf_start;
 772     while(block_num > 0 && this < ctx->alloc_end)
 773     {
 774         this += abs(this->val);
 775         block_num -= 1;
 776     }
 777     snprintf(buf, bufsize, "%8p: val: %4ld (%s)",
 778                             this, (long)this->val,
 779                             this->val > 0? this[3].name:"<unallocated>");
 780 }
 781
 782 #endif