FreeBSD/Linux Kernel Cross Reference
sys/kern/kalloc.c
1 /*
2 * Mach Operating System
3 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
4 * All Rights Reserved.
5 *
6 * Permission to use, copy, modify and distribute this software and its
7 * documentation is hereby granted, provided that both the copyright
8 * notice and this permission notice appear in all copies of the
9 * software, derivative works or modified versions, and any portions
10 * thereof, and that both notices appear in supporting documentation.
11 *
12 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
13 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
14 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
15 *
16 * Carnegie Mellon requests users of this software to return to
17 *
18 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
19 * School of Computer Science
20 * Carnegie Mellon University
21 * Pittsburgh PA 15213-3890
22 *
23 * any improvements or extensions that they make and grant Carnegie Mellon
24 * the rights to redistribute these changes.
25 */
26 /*
27 * HISTORY
28 * $Log: kalloc.c,v $
29 * Revision 2.11 92/08/03 17:37:50 jfriedl
30 * removed silly prototypes
31 * [92/08/02 jfriedl]
32 *
33 * Revision 2.10 92/05/21 17:14:22 jfriedl
34 * tried prototypes.
35 * [92/05/20 jfriedl]
36 *
37 * Revision 2.9 91/05/14 16:43:17 mrt
38 * Correcting copyright
39 *
40 * Revision 2.8 91/03/16 14:50:37 rpd
41 * Updated for new kmem_alloc interface.
42 * [91/03/03 rpd]
43 *
44 * Revision 2.7 91/02/05 17:27:22 mrt
45 * Changed to new Mach copyright
46 * [91/02/01 16:14:12 mrt]
47 *
48 * Revision 2.6 90/06/19 22:59:06 rpd
49 * Made the big kalloc zones collectable.
50 * [90/06/05 rpd]
51 *
52 * Revision 2.5 90/06/02 14:54:47 rpd
53 * Added kalloc_max, kalloc_map_size.
54 * [90/03/26 22:06:39 rpd]
55 *
56 * Revision 2.4 90/01/11 11:43:13 dbg
57 * De-lint.
58 * [89/12/06 dbg]
59 *
60 * Revision 2.3 89/09/08 11:25:51 dbg
61 * MACH_KERNEL: remove non-MACH data types.
62 * [89/07/11 dbg]
63 *
64 * Revision 2.2 89/08/31 16:18:59 rwd
65 * First Checkin
66 * [89/08/23 15:41:37 rwd]
67 *
68 * Revision 2.6 89/08/02 08:03:28 jsb
69 * Make all kalloc zones 8 MB big. (No more kalloc panics!)
70 * [89/08/01 14:10:17 jsb]
71 *
72 * Revision 2.4 89/04/05 13:03:10 rvb
73 * Guarantee a zone max of at least 100 elements or 10 pages
74 * which ever is greater. Afs (AllocDouble()) puts a great demand
75 * on the 2048 zone and used to blow away.
76 * [89/03/09 rvb]
77 *
78 * Revision 2.3 89/02/25 18:04:39 gm0w
79 * Changes for cleanup.
80 *
81 * Revision 2.2 89/01/18 02:07:04 jsb
82 * Give each kalloc zone a meaningful name (for panics);
83 * create a zone for each power of 2 between MINSIZE
84 * and PAGE_SIZE, instead of using (obsoleted) NQUEUES.
85 * [89/01/17 10:16:33 jsb]
86 *
87 *
88 * 13-Feb-88 John Seamons (jks) at NeXT
89 * Updated to use kmem routines instead of vmem routines.
90 *
91 * 21-Jun-85 Avadis Tevanian (avie) at Carnegie-Mellon University
92 * Created.
93 */
94 /*
95 * File: kern/kalloc.c
96 * Author: Avadis Tevanian, Jr.
97 * Date: 1985
98 *
99 * General kernel memory allocator. This allocator is designed
100 * to be used by the kernel to manage dynamic memory fast.
101 */
102
103 #include <mach/machine/vm_types.h>
104 #include <mach/vm_param.h>
105
106 #include <kern/zalloc.h>
107 #include <kern/kalloc.h>
108 #include <vm/vm_kern.h>
109 #include <vm/vm_object.h>
110 #include <vm/vm_map.h>
111
112
113
114 vm_map_t kalloc_map;
115 vm_size_t kalloc_map_size = 8 * 1024 * 1024;
116 vm_size_t kalloc_max;
117
118 /*
119 * All allocations of size less than kalloc_max are rounded to the
120 * next highest power of 2. This allocator is built on top of
121 * the zone allocator. A zone is created for each potential size
122 * that we are willing to get in small blocks.
123 *
124 * We assume that kalloc_max is not greater than 64K;
125 * thus 16 is a safe array size for k_zone and k_zone_name.
126 */
127
128 int first_k_zone = -1;
129 struct zone *k_zone[16];
130 static char *k_zone_name[16] = {
131 "kalloc.1", "kalloc.2",
132 "kalloc.4", "kalloc.8",
133 "kalloc.16", "kalloc.32",
134 "kalloc.64", "kalloc.128",
135 "kalloc.256", "kalloc.512",
136 "kalloc.1024", "kalloc.2048",
137 "kalloc.4096", "kalloc.8192",
138 "kalloc.16384", "kalloc.32768"
139 };
140
141 /*
142 * Max number of elements per zone. zinit rounds things up correctly
143 * Doing things this way permits each zone to have a different maximum size
144 * based on need, rather than just guessing; it also
145 * means its patchable in case you're wrong!
146 */
147 unsigned long k_zone_max[16] = {
148 1024, /* 1 Byte */
149 1024, /* 2 Byte */
150 1024, /* 4 Byte */
151 1024, /* 8 Byte */
152 1024, /* 16 Byte */
153 4096, /* 32 Byte */
154 4096, /* 64 Byte */
155 4096, /* 128 Byte */
156 4096, /* 256 Byte */
157 1024, /* 512 Byte */
158 1024, /* 1024 Byte */
159 1024, /* 2048 Byte */
160 1024, /* 4096 Byte */
161 4096, /* 8192 Byte */
162 64, /* 16384 Byte */
163 64, /* 32768 Byte */
164 };
165
166 /*
167 * Initialize the memory allocator. This should be called only
168 * once on a system wide basis (i.e. first processor to get here
169 * does the initialization).
170 *
171 * This initializes all of the zones.
172 */
173
174 void kalloc_init()
175 {
176 vm_offset_t min, max;
177 vm_size_t size;
178 register int i;
179
180 kalloc_map = kmem_suballoc(kernel_map, &min, &max,
181 kalloc_map_size, FALSE);
182
183 /*
184 * Ensure that zones up to size 8192 bytes exist.
185 * This is desirable because messages are allocated
186 * with kalloc, and messages up through size 8192 are common.
187 */
188
189 if (PAGE_SIZE < 16*1024)
190 kalloc_max = 16*1024;
191 else
192 kalloc_max = PAGE_SIZE;
193
194 /*
195 * Allocate a zone for each size we are going to handle.
196 * We specify non-paged memory.
197 */
198 for (i = 0, size = 1; size < kalloc_max; i++, size <<= 1) {
199 if (size < MINSIZE) {
200 k_zone[i] = 0;
201 continue;
202 }
203 if (size == MINSIZE) {
204 first_k_zone = i;
205 }
206 k_zone[i] = zinit(size, k_zone_max[i] * size, size,
207 FALSE, k_zone_name[i]);
208 if (size >= PAGE_SIZE)
209 zcollectable(k_zone[i]);
210 }
211 }
212
213 vm_offset_t kalloc(size)
214 vm_size_t size;
215 {
216 register int zindex;
217 register vm_size_t allocsize;
218 vm_offset_t addr;
219
220 /* compute the size of the block that we will actually allocate */
221
222 allocsize = size;
223 if (size < kalloc_max) {
224 allocsize = MINSIZE;
225 zindex = first_k_zone;
226 while (allocsize < size) {
227 allocsize <<= 1;
228 zindex++;
229 }
230 }
231
232 /*
233 * If our size is still small enough, check the queue for that size
234 * and allocate.
235 */
236
237 if (allocsize < kalloc_max) {
238 addr = zalloc(k_zone[zindex]);
239 } else {
240 if (kmem_alloc_wired(kalloc_map, &addr, allocsize)
241 != KERN_SUCCESS)
242 addr = 0;
243 }
244 return(addr);
245 }
246
247 vm_offset_t kget(size)
248 vm_size_t size;
249 {
250 register int zindex;
251 register vm_size_t allocsize;
252 vm_offset_t addr;
253
254 /* compute the size of the block that we will actually allocate */
255
256 allocsize = size;
257 if (size < kalloc_max) {
258 allocsize = MINSIZE;
259 zindex = first_k_zone;
260 while (allocsize < size) {
261 allocsize <<= 1;
262 zindex++;
263 }
264 }
265
266 /*
267 * If our size is still small enough, check the queue for that size
268 * and allocate.
269 */
270
271 if (allocsize < kalloc_max) {
272 addr = zget(k_zone[zindex]);
273 } else {
274 /* This will never work, so we might as well panic */
275 panic("kget");
276 }
277 return(addr);
278 }
279
280 void
281 kfree(data, size)
282 vm_offset_t data;
283 vm_size_t size;
284 {
285 register int zindex;
286 register vm_size_t freesize;
287
288 freesize = size;
289 if (size < kalloc_max) {
290 freesize = MINSIZE;
291 zindex = first_k_zone;
292 while (freesize < size) {
293 freesize <<= 1;
294 zindex++;
295 }
296 }
297
298 if (freesize < kalloc_max) {
299 zfree(k_zone[zindex], data);
300 } else {
301 kmem_free(kalloc_map, data, freesize);
302 }
303 }
Cache object: c2bb79049742e3ae6d96063990e8269d
|