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