2 * Copyright 2000, International Business Machines Corporation and others.
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
10 #include <afsconfig.h>
11 #include <afs/param.h>
15 #include "afs_atomlist.h"
17 #include "afs_atomlist.h"
21 * The afs_atomlist abstract data type is for efficiently allocating
22 * space for small structures.
24 * The atoms in an afs_atomlist are allocated in blocks. The blocks
25 * are chained together so that they can be freed when the afs_atomlist
26 * is destroyed. When a new block is allocated, its atoms are chained
27 * together and added to the free list of atoms.
29 * If the requested atom size is smaller than the size of a pointer,
30 * afs_atomlist_create() silently increases the atom size. If
31 * the atom size would result in incorrectly aligned pointers,
32 * afs_atomlist_create() silently increases the atom size as necessary.
34 * A block of atoms is organized as follows.
36 * ---------------------------------------------------------------
37 * | atom | atom | atom | ... | atom | nextblock | wasted space* |
38 * ---------------------------------------------------------------
39 * \____ atoms_per_block atoms ______/
41 * (*) A block may or may not contain wasted space at the end. The
42 * amount of wasted space depends on the size of a block, the size of an
43 * atom, and the size of the pointer to the next block. For instance,
44 * if a block is 4096 bytes, an atom is 12 bytes, and a pointer is 4
45 * bytes, there is no wasted space in a block.
47 * The pointer to the next block is stored AFTER all the atoms in the
50 * If we put the pointer to the next block before the atoms,
51 * followed immediately by the atoms, we would be assuming that the
52 * atoms could be aligned on a pointer boundary.
54 * If we tried to solve the alignment problem by allocating an entire
55 * atom for the pointer to the next block, we might waste space
56 * gratuitously. Say a block is 4096 bytes, an atom is 24 bytes, and a
57 * pointer is 8 bytes. In this case a block can hold 170 atoms, with 16
58 * bytes left over. This isn't enough space for another atom, but it is
59 * enough space for the pointer to the next block. There is no need to
60 * use one of the atoms to store the pointer to the next block.
62 * So, we store the pointer to the next block after the end of the atoms
63 * in the block. In the worst case, the block size is an exact multiple
64 * of the atom size, and we waste an entire atom to store the pointer to
65 * the next block. But we hope it is more typical that there is enough
66 * extra space after the atoms to store the pointer to the next block.
68 * A more sophisticated scheme would keep the pointers to the atom
69 * blocks in a separate list of blocks. It would eliminate the
70 * fragmentation of the atom blocks in the case where the block size
71 * is a multiple of the atom size. However, it is more complicated to
72 * understand and to implement, so I chose not to do it at this time.
73 * If fragmentation turns out to be a serious enough issue, we can
74 * change the afs_atomlist implementation without affecting its users.
80 size_t atoms_per_block
;
81 void *(*allocate
) (size_t n
);
82 void (*deallocate
) (void *p
, size_t n
);
83 void *atom_head
; /* pointer to head of atom free list */
84 void *block_head
; /* pointer to block list */
88 afs_atomlist_create(size_t atom_size
, size_t block_size
,
89 void *(*allocate
) (size_t n
)
90 , void (*deallocate
) (void *p
, size_t n
)
94 size_t atoms_per_block
;
98 * Atoms must be at least as big as a pointer in order for
99 * our implementation of the atom free list to work.
101 if (atom_size
< sizeof(void *)) {
102 atom_size
= sizeof(void *);
106 * Atoms must be a multiple of the size of a pointer
107 * so that the pointers in the atom free list will be
110 if (atom_size
% sizeof(void *) != (size_t) 0) {
111 size_t pad
= sizeof(void *) - (atom_size
% sizeof(void *));
116 * Blocks are the unit of memory allocation.
118 * 1) Atoms are allocated out of blocks.
120 * 2) sizeof(void *) bytes in each block, aligned on a sizeof(void *)
121 * boundary, are used to chain together the blocks so that they can
122 * be freed later. This reduces the space in each block for atoms.
123 * It is intended that atoms should be small relative to the size of
124 * a block, so this should not be a problem.
126 * At a minimum, a block must be big enough for one atom and
127 * a pointer to the next block.
129 if (block_size
< atom_size
+ sizeof(void *))
132 atoms_per_block
= block_size
/ atom_size
;
133 extra_space
= block_size
- (atoms_per_block
* atom_size
);
134 if (extra_space
< sizeof(void *)) {
135 if (atoms_per_block
< (size_t) 2) {
136 return 0; /* INTERNAL ERROR! */
141 al
= allocate(sizeof *al
);
145 al
->atom_size
= atom_size
;
146 al
->block_size
= block_size
;
147 al
->allocate
= allocate
;
148 al
->deallocate
= deallocate
;
151 al
->atoms_per_block
= atoms_per_block
;
157 afs_atomlist_destroy(afs_atomlist
* al
)
162 for (cur
= al
->block_head
; cur
; cur
= next
) {
163 next
= *(void **)((char *)cur
+ al
->atoms_per_block
* al
->atom_size
);
164 al
->deallocate(cur
, al
->block_size
);
166 al
->deallocate(al
, sizeof *al
);
170 afs_atomlist_get(afs_atomlist
* al
)
174 /* allocate a new block if necessary */
175 if (!al
->atom_head
) {
180 block
= al
->allocate(al
->block_size
);
185 /* add this block to the chain of allocated blocks */
186 *(void **)((char *)block
+ al
->atoms_per_block
* al
->atom_size
) =
188 al
->block_head
= block
;
190 /* add this block's atoms to the atom free list */
192 for (i
= 0; i
+ 1 < al
->atoms_per_block
; i
++) {
193 *(void **)p
= (char *)p
+ al
->atom_size
;
194 p
= (char *)p
+ al
->atom_size
;
197 al
->atom_head
= block
;
200 if (!al
->atom_head
) {
201 return 0; /* INTERNAL ERROR */
204 data
= al
->atom_head
;
205 al
->atom_head
= *(void **)data
;
211 afs_atomlist_put(afs_atomlist
* al
, void *data
)
213 *(void **)data
= al
->atom_head
;
214 al
->atom_head
= data
;