src/util/afs_atomlist.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afsconfig.h>
  11 #include <afs/param.h>
  12
  13 RCSID
  14     ("$Header$");
  15
  16 #ifdef KERNEL
  17 #include "afs_atomlist.h"
  18 #else /* KERNEL */
  19 #include "afs_atomlist.h"
  20 #endif /* KERNEL */
  21
  22 /*
  23  * The afs_atomlist abstract data type is for efficiently allocating
  24  * space for small structures.
  25  *
  26  * The atoms in an afs_atomlist are allocated in blocks.  The blocks
  27  * are chained together so that they can be freed when the afs_atomlist
  28  * is destroyed.  When a new block is allocated, its atoms are chained
  29  * together and added to the free list of atoms.
  30  *
  31  * If the requested atom size is smaller than the size of a pointer,
  32  * afs_atomlist_create() silently increases the atom size.  If
  33  * the atom size would result in incorrectly aligned pointers,
  34  * afs_atomlist_create() silently increases the atom size as necessary.
  35  *
  36  * A block of atoms is organized as follows.
  37  *
  38  * ---------------------------------------------------------------
  39  * | atom | atom | atom | ... | atom | nextblock | wasted space* |
  40  * ---------------------------------------------------------------
  41  * \____ atoms_per_block atoms ______/
  42  *
  43  * (*) A block may or may not contain wasted space at the end.  The
  44  * amount of wasted space depends on the size of a block, the size of an
  45  * atom, and the size of the pointer to the next block.  For instance,
  46  * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4
  47  * bytes, there is no wasted space in a block.
  48  *
  49  * The pointer to the next block is stored AFTER all the atoms in the
  50  * block.  Here's why.
  51  *
  52  * If we put the pointer to the next block before the atoms,
  53  * followed immediately by the atoms, we would be assuming that the
  54  * atoms could be aligned on a pointer boundary.
  55  *
  56  * If we tried to solve the alignment problem by allocating an entire
  57  * atom for the pointer to the next block, we might waste space
  58  * gratuitously.  Say a block is 4096 bytes, an atom is 24 bytes, and a
  59  * pointer is 8 bytes.  In this case a block can hold 170 atoms, with 16
  60  * bytes left over.  This isn't enough space for another atom, but it is
  61  * enough space for the pointer to the next block.  There is no need to
  62  * use one of the atoms to store the pointer to the next block.
  63  *
  64  * So, we store the pointer to the next block after the end of the atoms
  65  * in the block.  In the worst case, the block size is an exact multiple
  66  * of the atom size, and we waste an entire atom to store the pointer to
  67  * the next block.  But we hope it is more typical that there is enough
  68  * extra space after the atoms to store the pointer to the next block.
  69  *
  70  * A more sophisticated scheme would keep the pointers to the atom
  71  * blocks in a separate list of blocks.  It would eliminate the
  72  * fragmentation of the atom blocks in the case where the block size
  73  * is a multiple of the atom size.  However, it is more complicated to
  74  * understand and to implement, so I chose not to do it at this time.
  75  * If fragmentation turns out to be a serious enough issue, we can
  76  * change the afs_atomlist implementation without affecting its users.
  77  */
  78
  79 struct afs_atomlist {
  80     size_t atom_size;
  81     size_t block_size;
  82     size_t atoms_per_block;
  83     void *(*allocate) (size_t n);
  84     void (*deallocate) (void *p, size_t n);
  85     void *atom_head;            /* pointer to head of atom free list */
  86     void *block_head;           /* pointer to block list */
  87 };
  88
  89 afs_atomlist *
  90 afs_atomlist_create(size_t atom_size, size_t block_size,
  91                     void *(*allocate) (size_t n)
  92                     , void (*deallocate) (void *p, size_t n)
  93     )
  94 {
  95     afs_atomlist *al;
  96     size_t atoms_per_block;
  97     size_t extra_space;
  98
  99     /*
 100      * Atoms must be at least as big as a pointer in order for
 101      * our implementation of the atom free list to work.
 102      */
 103     if (atom_size < sizeof(void *)) {
 104         atom_size = sizeof(void *);
 105     }
 106
 107     /*
 108      * Atoms must be a multiple of the size of a pointer
 109      * so that the pointers in the atom free list will be
 110      * properly aligned.
 111      */
 112     if (atom_size % sizeof(void *) != (size_t) 0) {
 113         size_t pad = sizeof(void *) - (atom_size % sizeof(void *));
 114         atom_size += pad;
 115     }
 116
 117     /*
 118      * Blocks are the unit of memory allocation.
 119      *
 120      * 1) Atoms are allocated out of blocks.
 121      *
 122      * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *)
 123      * boundary, are used to chain together the blocks so that they can
 124      * be freed later.  This reduces the space in each block for atoms.
 125      * It is intended that atoms should be small relative to the size of
 126      * a block, so this should not be a problem.
 127      *
 128      * At a minimum, a block must be big enough for one atom and
 129      * a pointer to the next block.
 130      */
 131     if (block_size < atom_size + sizeof(void *))
 132         return 0;
 133
 134     atoms_per_block = block_size / atom_size;
 135     extra_space = block_size - (atoms_per_block * atom_size);
 136     if (extra_space < sizeof(void *)) {
 137         if (atoms_per_block < (size_t) 2) {
 138             return 0;           /* INTERNAL ERROR! */
 139         }
 140         atoms_per_block--;
 141     }
 142
 143     al = allocate(sizeof *al);
 144     if (!al)
 145         return 0;
 146
 147     al->atom_size = atom_size;
 148     al->block_size = block_size;
 149     al->allocate = allocate;
 150     al->deallocate = deallocate;
 151     al->atom_head = 0;
 152     al->block_head = 0;
 153     al->atoms_per_block = atoms_per_block;
 154
 155     return al;
 156 }
 157
 158 void
 159 afs_atomlist_destroy(afs_atomlist * al)
 160 {
 161     void *cur;
 162     void *next;
 163
 164     for (cur = al->block_head; cur; cur = next) {
 165         next = *(void **)((char *)cur + al->atoms_per_block * al->atom_size);
 166         al->deallocate(cur, al->block_size);
 167     }
 168     al->deallocate(al, sizeof *al);
 169 }
 170
 171 void *
 172 afs_atomlist_get(afs_atomlist * al)
 173 {
 174     void *data;
 175
 176     /* allocate a new block if necessary */
 177     if (!al->atom_head) {
 178         void *block;
 179         void *p;
 180         size_t i;
 181
 182         block = al->allocate(al->block_size);
 183         if (!block) {
 184             return 0;
 185         }
 186
 187         /* add this block to the chain of allocated blocks */
 188         *(void **)((char *)block + al->atoms_per_block * al->atom_size) =
 189             al->block_head;
 190         al->block_head = block;
 191
 192         /* add this block's atoms to the atom free list */
 193         p = block;
 194         for (i = 0; i + 1 < al->atoms_per_block; i++) {
 195             *(void **)p = (char *)p + al->atom_size;
 196             p = (char *)p + al->atom_size;
 197         }
 198         *(void **)p = 0;
 199         al->atom_head = block;
 200     }
 201
 202     if (!al->atom_head) {
 203         return 0;               /* INTERNAL ERROR */
 204     }
 205
 206     data = al->atom_head;
 207     al->atom_head = *(void **)data;
 208
 209     return data;
 210 }
 211
 212 void
 213 afs_atomlist_put(afs_atomlist * al, void *data)
 214 {
 215     *(void **)data = al->atom_head;
 216     al->atom_head = data;
 217 }