Commit | Line | Data |
---|---|---|
805e021f CE |
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 | ||
14 | #ifdef KERNEL | |
15 | #include "afs_atomlist.h" | |
16 | #else /* KERNEL */ | |
17 | #include "afs_atomlist.h" | |
18 | #endif /* KERNEL */ | |
19 | ||
20 | /* | |
21 | * The afs_atomlist abstract data type is for efficiently allocating | |
22 | * space for small structures. | |
23 | * | |
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. | |
28 | * | |
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. | |
33 | * | |
34 | * A block of atoms is organized as follows. | |
35 | * | |
36 | * --------------------------------------------------------------- | |
37 | * | atom | atom | atom | ... | atom | nextblock | wasted space* | | |
38 | * --------------------------------------------------------------- | |
39 | * \____ atoms_per_block atoms ______/ | |
40 | * | |
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. | |
46 | * | |
47 | * The pointer to the next block is stored AFTER all the atoms in the | |
48 | * block. Here's why. | |
49 | * | |
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. | |
53 | * | |
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. | |
61 | * | |
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. | |
67 | * | |
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. | |
75 | */ | |
76 | ||
77 | struct afs_atomlist { | |
78 | size_t atom_size; | |
79 | size_t block_size; | |
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 */ | |
85 | }; | |
86 | ||
87 | afs_atomlist * | |
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) | |
91 | ) | |
92 | { | |
93 | afs_atomlist *al; | |
94 | size_t atoms_per_block; | |
95 | size_t extra_space; | |
96 | ||
97 | /* | |
98 | * Atoms must be at least as big as a pointer in order for | |
99 | * our implementation of the atom free list to work. | |
100 | */ | |
101 | if (atom_size < sizeof(void *)) { | |
102 | atom_size = sizeof(void *); | |
103 | } | |
104 | ||
105 | /* | |
106 | * Atoms must be a multiple of the size of a pointer | |
107 | * so that the pointers in the atom free list will be | |
108 | * properly aligned. | |
109 | */ | |
110 | if (atom_size % sizeof(void *) != (size_t) 0) { | |
111 | size_t pad = sizeof(void *) - (atom_size % sizeof(void *)); | |
112 | atom_size += pad; | |
113 | } | |
114 | ||
115 | /* | |
116 | * Blocks are the unit of memory allocation. | |
117 | * | |
118 | * 1) Atoms are allocated out of blocks. | |
119 | * | |
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. | |
125 | * | |
126 | * At a minimum, a block must be big enough for one atom and | |
127 | * a pointer to the next block. | |
128 | */ | |
129 | if (block_size < atom_size + sizeof(void *)) | |
130 | return 0; | |
131 | ||
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! */ | |
137 | } | |
138 | atoms_per_block--; | |
139 | } | |
140 | ||
141 | al = allocate(sizeof *al); | |
142 | if (!al) | |
143 | return 0; | |
144 | ||
145 | al->atom_size = atom_size; | |
146 | al->block_size = block_size; | |
147 | al->allocate = allocate; | |
148 | al->deallocate = deallocate; | |
149 | al->atom_head = 0; | |
150 | al->block_head = 0; | |
151 | al->atoms_per_block = atoms_per_block; | |
152 | ||
153 | return al; | |
154 | } | |
155 | ||
156 | void | |
157 | afs_atomlist_destroy(afs_atomlist * al) | |
158 | { | |
159 | void *cur; | |
160 | void *next; | |
161 | ||
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); | |
165 | } | |
166 | al->deallocate(al, sizeof *al); | |
167 | } | |
168 | ||
169 | void * | |
170 | afs_atomlist_get(afs_atomlist * al) | |
171 | { | |
172 | void *data; | |
173 | ||
174 | /* allocate a new block if necessary */ | |
175 | if (!al->atom_head) { | |
176 | void *block; | |
177 | void *p; | |
178 | size_t i; | |
179 | ||
180 | block = al->allocate(al->block_size); | |
181 | if (!block) { | |
182 | return 0; | |
183 | } | |
184 | ||
185 | /* add this block to the chain of allocated blocks */ | |
186 | *(void **)((char *)block + al->atoms_per_block * al->atom_size) = | |
187 | al->block_head; | |
188 | al->block_head = block; | |
189 | ||
190 | /* add this block's atoms to the atom free list */ | |
191 | p = block; | |
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; | |
195 | } | |
196 | *(void **)p = 0; | |
197 | al->atom_head = block; | |
198 | } | |
199 | ||
200 | if (!al->atom_head) { | |
201 | return 0; /* INTERNAL ERROR */ | |
202 | } | |
203 | ||
204 | data = al->atom_head; | |
205 | al->atom_head = *(void **)data; | |
206 | ||
207 | return data; | |
208 | } | |
209 | ||
210 | void | |
211 | afs_atomlist_put(afs_atomlist * al, void *data) | |
212 | { | |
213 | *(void **)data = al->atom_head; | |
214 | al->atom_head = data; | |
215 | } |