kern_malloc.c revision 1.72 1 1.72 thorpej /* $NetBSD: kern_malloc.c,v 1.72 2002/08/25 21:19:41 thorpej Exp $ */
2 1.9 cgd
3 1.1 cgd /*
4 1.37 christos * Copyright (c) 1996 Christopher G. Demetriou. All rights reserved.
5 1.8 cgd * Copyright (c) 1987, 1991, 1993
6 1.8 cgd * The Regents of the University of California. All rights reserved.
7 1.1 cgd *
8 1.1 cgd * Redistribution and use in source and binary forms, with or without
9 1.1 cgd * modification, are permitted provided that the following conditions
10 1.1 cgd * are met:
11 1.1 cgd * 1. Redistributions of source code must retain the above copyright
12 1.1 cgd * notice, this list of conditions and the following disclaimer.
13 1.1 cgd * 2. Redistributions in binary form must reproduce the above copyright
14 1.1 cgd * notice, this list of conditions and the following disclaimer in the
15 1.1 cgd * documentation and/or other materials provided with the distribution.
16 1.1 cgd * 3. All advertising materials mentioning features or use of this software
17 1.1 cgd * must display the following acknowledgement:
18 1.1 cgd * This product includes software developed by the University of
19 1.1 cgd * California, Berkeley and its contributors.
20 1.1 cgd * 4. Neither the name of the University nor the names of its contributors
21 1.1 cgd * may be used to endorse or promote products derived from this software
22 1.1 cgd * without specific prior written permission.
23 1.1 cgd *
24 1.1 cgd * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 1.1 cgd * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 1.1 cgd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 1.1 cgd * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 1.1 cgd * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 1.1 cgd * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 1.1 cgd * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 1.1 cgd * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 1.1 cgd * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 1.1 cgd * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 1.1 cgd * SUCH DAMAGE.
35 1.1 cgd *
36 1.32 fvdl * @(#)kern_malloc.c 8.4 (Berkeley) 5/20/95
37 1.1 cgd */
38 1.64 lukem
39 1.64 lukem #include <sys/cdefs.h>
40 1.72 thorpej __KERNEL_RCSID(0, "$NetBSD: kern_malloc.c,v 1.72 2002/08/25 21:19:41 thorpej Exp $");
41 1.31 mrg
42 1.33 thorpej #include "opt_lockdebug.h"
43 1.1 cgd
44 1.7 mycroft #include <sys/param.h>
45 1.7 mycroft #include <sys/proc.h>
46 1.8 cgd #include <sys/map.h>
47 1.7 mycroft #include <sys/kernel.h>
48 1.7 mycroft #include <sys/malloc.h>
49 1.12 christos #include <sys/systm.h>
50 1.24 thorpej
51 1.28 mrg #include <uvm/uvm_extern.h>
52 1.28 mrg
53 1.61 thorpej static struct vm_map kmem_map_store;
54 1.58 chs struct vm_map *kmem_map = NULL;
55 1.28 mrg
56 1.49 thorpej #include "opt_kmempages.h"
57 1.49 thorpej
58 1.49 thorpej #ifdef NKMEMCLUSTERS
59 1.52 sommerfe #error NKMEMCLUSTERS is obsolete; remove it from your kernel config file and use NKMEMPAGES instead or let the kernel auto-size
60 1.49 thorpej #endif
61 1.49 thorpej
62 1.49 thorpej /*
63 1.49 thorpej * Default number of pages in kmem_map. We attempt to calculate this
64 1.49 thorpej * at run-time, but allow it to be either patched or set in the kernel
65 1.49 thorpej * config file.
66 1.49 thorpej */
67 1.49 thorpej #ifndef NKMEMPAGES
68 1.49 thorpej #define NKMEMPAGES 0
69 1.49 thorpej #endif
70 1.49 thorpej int nkmempages = NKMEMPAGES;
71 1.49 thorpej
72 1.49 thorpej /*
73 1.49 thorpej * Defaults for lower- and upper-bounds for the kmem_map page count.
74 1.49 thorpej * Can be overridden by kernel config options.
75 1.49 thorpej */
76 1.49 thorpej #ifndef NKMEMPAGES_MIN
77 1.49 thorpej #define NKMEMPAGES_MIN NKMEMPAGES_MIN_DEFAULT
78 1.49 thorpej #endif
79 1.49 thorpej
80 1.49 thorpej #ifndef NKMEMPAGES_MAX
81 1.49 thorpej #define NKMEMPAGES_MAX NKMEMPAGES_MAX_DEFAULT
82 1.49 thorpej #endif
83 1.49 thorpej
84 1.24 thorpej #include "opt_kmemstats.h"
85 1.27 thorpej #include "opt_malloclog.h"
86 1.71 fvdl #include "opt_malloc_debug.h"
87 1.12 christos
88 1.1 cgd struct kmembuckets bucket[MINBUCKET + 16];
89 1.8 cgd struct kmemstats kmemstats[M_LAST];
90 1.1 cgd struct kmemusage *kmemusage;
91 1.1 cgd char *kmembase, *kmemlimit;
92 1.57 jdolecek const char * const memname[] = INITKMEMNAMES;
93 1.1 cgd
94 1.27 thorpej #ifdef MALLOCLOG
95 1.27 thorpej #ifndef MALLOCLOGSIZE
96 1.27 thorpej #define MALLOCLOGSIZE 100000
97 1.27 thorpej #endif
98 1.27 thorpej
99 1.27 thorpej struct malloclog {
100 1.27 thorpej void *addr;
101 1.27 thorpej long size;
102 1.27 thorpej int type;
103 1.27 thorpej int action;
104 1.27 thorpej const char *file;
105 1.27 thorpej long line;
106 1.27 thorpej } malloclog[MALLOCLOGSIZE];
107 1.27 thorpej
108 1.27 thorpej long malloclogptr;
109 1.27 thorpej
110 1.69 enami static void domlog(void *, long, int, int, const char *, long);
111 1.69 enami static void hitmlog(void *);
112 1.27 thorpej
113 1.27 thorpej static void
114 1.69 enami domlog(void *a, long size, int type, int action, const char *file, long line)
115 1.27 thorpej {
116 1.27 thorpej
117 1.27 thorpej malloclog[malloclogptr].addr = a;
118 1.27 thorpej malloclog[malloclogptr].size = size;
119 1.27 thorpej malloclog[malloclogptr].type = type;
120 1.27 thorpej malloclog[malloclogptr].action = action;
121 1.27 thorpej malloclog[malloclogptr].file = file;
122 1.27 thorpej malloclog[malloclogptr].line = line;
123 1.27 thorpej malloclogptr++;
124 1.27 thorpej if (malloclogptr >= MALLOCLOGSIZE)
125 1.27 thorpej malloclogptr = 0;
126 1.27 thorpej }
127 1.27 thorpej
128 1.27 thorpej static void
129 1.69 enami hitmlog(void *a)
130 1.27 thorpej {
131 1.27 thorpej struct malloclog *lp;
132 1.27 thorpej long l;
133 1.27 thorpej
134 1.69 enami #define PRT do { \
135 1.27 thorpej if (malloclog[l].addr == a && malloclog[l].action) { \
136 1.27 thorpej lp = &malloclog[l]; \
137 1.27 thorpej printf("malloc log entry %ld:\n", l); \
138 1.27 thorpej printf("\taddr = %p\n", lp->addr); \
139 1.27 thorpej printf("\tsize = %ld\n", lp->size); \
140 1.27 thorpej printf("\ttype = %s\n", memname[lp->type]); \
141 1.27 thorpej printf("\taction = %s\n", lp->action == 1 ? "alloc" : "free"); \
142 1.27 thorpej printf("\tfile = %s\n", lp->file); \
143 1.27 thorpej printf("\tline = %ld\n", lp->line); \
144 1.69 enami } \
145 1.69 enami } while (/* CONSTCOND */0)
146 1.27 thorpej
147 1.27 thorpej for (l = malloclogptr; l < MALLOCLOGSIZE; l++)
148 1.69 enami PRT;
149 1.27 thorpej
150 1.27 thorpej for (l = 0; l < malloclogptr; l++)
151 1.69 enami PRT;
152 1.27 thorpej }
153 1.27 thorpej #endif /* MALLOCLOG */
154 1.27 thorpej
155 1.8 cgd #ifdef DIAGNOSTIC
156 1.8 cgd /*
157 1.8 cgd * This structure provides a set of masks to catch unaligned frees.
158 1.8 cgd */
159 1.57 jdolecek const long addrmask[] = { 0,
160 1.8 cgd 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
161 1.8 cgd 0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff,
162 1.8 cgd 0x000001ff, 0x000003ff, 0x000007ff, 0x00000fff,
163 1.8 cgd 0x00001fff, 0x00003fff, 0x00007fff, 0x0000ffff,
164 1.8 cgd };
165 1.8 cgd
166 1.8 cgd /*
167 1.8 cgd * The WEIRD_ADDR is used as known text to copy into free objects so
168 1.8 cgd * that modifications after frees can be detected.
169 1.8 cgd */
170 1.69 enami #define WEIRD_ADDR ((unsigned) 0xdeadbeef)
171 1.55 chs #ifdef DEBUG
172 1.69 enami #define MAX_COPY PAGE_SIZE
173 1.55 chs #else
174 1.69 enami #define MAX_COPY 32
175 1.55 chs #endif
176 1.8 cgd
177 1.8 cgd /*
178 1.11 cgd * Normally the freelist structure is used only to hold the list pointer
179 1.11 cgd * for free objects. However, when running with diagnostics, the first
180 1.11 cgd * 8 bytes of the structure is unused except for diagnostic information,
181 1.11 cgd * and the free list pointer is at offst 8 in the structure. Since the
182 1.11 cgd * first 8 bytes is the portion of the structure most often modified, this
183 1.11 cgd * helps to detect memory reuse problems and avoid free list corruption.
184 1.8 cgd */
185 1.8 cgd struct freelist {
186 1.11 cgd int32_t spare0;
187 1.11 cgd int16_t type;
188 1.11 cgd int16_t spare1;
189 1.8 cgd caddr_t next;
190 1.8 cgd };
191 1.8 cgd #else /* !DIAGNOSTIC */
192 1.8 cgd struct freelist {
193 1.8 cgd caddr_t next;
194 1.8 cgd };
195 1.8 cgd #endif /* DIAGNOSTIC */
196 1.8 cgd
197 1.1 cgd /*
198 1.1 cgd * Allocate a block of memory
199 1.1 cgd */
200 1.27 thorpej #ifdef MALLOCLOG
201 1.27 thorpej void *
202 1.69 enami _malloc(unsigned long size, int type, int flags, const char *file, long line)
203 1.27 thorpej #else
204 1.1 cgd void *
205 1.69 enami malloc(unsigned long size, int type, int flags)
206 1.27 thorpej #endif /* MALLOCLOG */
207 1.1 cgd {
208 1.50 augustss struct kmembuckets *kbp;
209 1.50 augustss struct kmemusage *kup;
210 1.50 augustss struct freelist *freep;
211 1.5 andrew long indx, npg, allocsize;
212 1.1 cgd int s;
213 1.1 cgd caddr_t va, cp, savedlist;
214 1.8 cgd #ifdef DIAGNOSTIC
215 1.11 cgd int32_t *end, *lp;
216 1.8 cgd int copysize;
217 1.26 mycroft const char *savedtype;
218 1.8 cgd #endif
219 1.1 cgd #ifdef KMEMSTATS
220 1.50 augustss struct kmemstats *ksp = &kmemstats[type];
221 1.1 cgd
222 1.51 thorpej if (__predict_false(((unsigned long)type) > M_LAST))
223 1.1 cgd panic("malloc - bogus type");
224 1.1 cgd #endif
225 1.59 thorpej #ifdef LOCKDEBUG
226 1.59 thorpej if ((flags & M_NOWAIT) == 0)
227 1.59 thorpej simple_lock_only_held(NULL, "malloc");
228 1.59 thorpej #endif
229 1.62 thorpej #ifdef MALLOC_DEBUG
230 1.62 thorpej if (debug_malloc(size, type, flags, (void **) &va))
231 1.62 thorpej return ((void *) va);
232 1.62 thorpej #endif
233 1.1 cgd indx = BUCKETINDX(size);
234 1.1 cgd kbp = &bucket[indx];
235 1.56 thorpej s = splvm();
236 1.1 cgd #ifdef KMEMSTATS
237 1.1 cgd while (ksp->ks_memuse >= ksp->ks_limit) {
238 1.1 cgd if (flags & M_NOWAIT) {
239 1.1 cgd splx(s);
240 1.1 cgd return ((void *) NULL);
241 1.1 cgd }
242 1.1 cgd if (ksp->ks_limblocks < 65535)
243 1.1 cgd ksp->ks_limblocks++;
244 1.1 cgd tsleep((caddr_t)ksp, PSWP+2, memname[type], 0);
245 1.1 cgd }
246 1.8 cgd ksp->ks_size |= 1 << indx;
247 1.8 cgd #endif
248 1.8 cgd #ifdef DIAGNOSTIC
249 1.8 cgd copysize = 1 << indx < MAX_COPY ? 1 << indx : MAX_COPY;
250 1.1 cgd #endif
251 1.1 cgd if (kbp->kb_next == NULL) {
252 1.8 cgd kbp->kb_last = NULL;
253 1.1 cgd if (size > MAXALLOCSAVE)
254 1.66 enami allocsize = round_page(size);
255 1.1 cgd else
256 1.1 cgd allocsize = 1 << indx;
257 1.47 ragge npg = btoc(allocsize);
258 1.63 chs va = (caddr_t) uvm_km_kmemalloc(kmem_map, NULL,
259 1.69 enami (vsize_t)ctob(npg),
260 1.69 enami (flags & M_NOWAIT) ? UVM_KMF_NOWAIT : 0);
261 1.51 thorpej if (__predict_false(va == NULL)) {
262 1.17 cgd /*
263 1.17 cgd * Kmem_malloc() can return NULL, even if it can
264 1.17 cgd * wait, if there is no map space avaiable, because
265 1.17 cgd * it can't fix that problem. Neither can we,
266 1.17 cgd * right now. (We should release pages which
267 1.17 cgd * are completely free and which are in buckets
268 1.17 cgd * with too many free elements.)
269 1.17 cgd */
270 1.68 jdolecek if ((flags & (M_NOWAIT|M_CANFAIL)) == 0)
271 1.17 cgd panic("malloc: out of space in kmem_map");
272 1.6 cgd splx(s);
273 1.6 cgd return ((void *) NULL);
274 1.1 cgd }
275 1.1 cgd #ifdef KMEMSTATS
276 1.1 cgd kbp->kb_total += kbp->kb_elmpercl;
277 1.1 cgd #endif
278 1.1 cgd kup = btokup(va);
279 1.1 cgd kup->ku_indx = indx;
280 1.1 cgd if (allocsize > MAXALLOCSAVE) {
281 1.1 cgd if (npg > 65535)
282 1.1 cgd panic("malloc: allocation too large");
283 1.1 cgd kup->ku_pagecnt = npg;
284 1.1 cgd #ifdef KMEMSTATS
285 1.1 cgd ksp->ks_memuse += allocsize;
286 1.1 cgd #endif
287 1.1 cgd goto out;
288 1.1 cgd }
289 1.1 cgd #ifdef KMEMSTATS
290 1.1 cgd kup->ku_freecnt = kbp->kb_elmpercl;
291 1.1 cgd kbp->kb_totalfree += kbp->kb_elmpercl;
292 1.1 cgd #endif
293 1.1 cgd /*
294 1.1 cgd * Just in case we blocked while allocating memory,
295 1.1 cgd * and someone else also allocated memory for this
296 1.1 cgd * bucket, don't assume the list is still empty.
297 1.1 cgd */
298 1.1 cgd savedlist = kbp->kb_next;
299 1.49 thorpej kbp->kb_next = cp = va + (npg << PAGE_SHIFT) - allocsize;
300 1.8 cgd for (;;) {
301 1.8 cgd freep = (struct freelist *)cp;
302 1.8 cgd #ifdef DIAGNOSTIC
303 1.8 cgd /*
304 1.8 cgd * Copy in known text to detect modification
305 1.8 cgd * after freeing.
306 1.8 cgd */
307 1.11 cgd end = (int32_t *)&cp[copysize];
308 1.11 cgd for (lp = (int32_t *)cp; lp < end; lp++)
309 1.8 cgd *lp = WEIRD_ADDR;
310 1.8 cgd freep->type = M_FREE;
311 1.8 cgd #endif /* DIAGNOSTIC */
312 1.8 cgd if (cp <= va)
313 1.8 cgd break;
314 1.8 cgd cp -= allocsize;
315 1.8 cgd freep->next = cp;
316 1.8 cgd }
317 1.8 cgd freep->next = savedlist;
318 1.8 cgd if (kbp->kb_last == NULL)
319 1.8 cgd kbp->kb_last = (caddr_t)freep;
320 1.1 cgd }
321 1.1 cgd va = kbp->kb_next;
322 1.8 cgd kbp->kb_next = ((struct freelist *)va)->next;
323 1.8 cgd #ifdef DIAGNOSTIC
324 1.8 cgd freep = (struct freelist *)va;
325 1.8 cgd savedtype = (unsigned)freep->type < M_LAST ?
326 1.8 cgd memname[freep->type] : "???";
327 1.29 chs if (kbp->kb_next) {
328 1.29 chs int rv;
329 1.35 eeh vaddr_t addr = (vaddr_t)kbp->kb_next;
330 1.29 chs
331 1.43 thorpej vm_map_lock(kmem_map);
332 1.29 chs rv = uvm_map_checkprot(kmem_map, addr,
333 1.69 enami addr + sizeof(struct freelist), VM_PROT_WRITE);
334 1.43 thorpej vm_map_unlock(kmem_map);
335 1.29 chs
336 1.51 thorpej if (__predict_false(rv == 0)) {
337 1.69 enami printf("Data modified on freelist: "
338 1.69 enami "word %ld of object %p size %ld previous type %s "
339 1.69 enami "(invalid addr %p)\n",
340 1.41 mrg (long)((int32_t *)&kbp->kb_next - (int32_t *)kbp),
341 1.69 enami va, size, savedtype, kbp->kb_next);
342 1.27 thorpej #ifdef MALLOCLOG
343 1.41 mrg hitmlog(va);
344 1.27 thorpej #endif
345 1.41 mrg kbp->kb_next = NULL;
346 1.29 chs }
347 1.8 cgd }
348 1.11 cgd
349 1.11 cgd /* Fill the fields that we've used with WEIRD_ADDR */
350 1.8 cgd #if BYTE_ORDER == BIG_ENDIAN
351 1.8 cgd freep->type = WEIRD_ADDR >> 16;
352 1.8 cgd #endif
353 1.8 cgd #if BYTE_ORDER == LITTLE_ENDIAN
354 1.8 cgd freep->type = (short)WEIRD_ADDR;
355 1.8 cgd #endif
356 1.11 cgd end = (int32_t *)&freep->next +
357 1.11 cgd (sizeof(freep->next) / sizeof(int32_t));
358 1.11 cgd for (lp = (int32_t *)&freep->next; lp < end; lp++)
359 1.11 cgd *lp = WEIRD_ADDR;
360 1.11 cgd
361 1.11 cgd /* and check that the data hasn't been modified. */
362 1.11 cgd end = (int32_t *)&va[copysize];
363 1.11 cgd for (lp = (int32_t *)va; lp < end; lp++) {
364 1.51 thorpej if (__predict_true(*lp == WEIRD_ADDR))
365 1.8 cgd continue;
366 1.69 enami printf("Data modified on freelist: "
367 1.69 enami "word %ld of object %p size %ld previous type %s "
368 1.69 enami "(0x%x != 0x%x)\n",
369 1.69 enami (long)(lp - (int32_t *)va), va, size,
370 1.21 christos savedtype, *lp, WEIRD_ADDR);
371 1.27 thorpej #ifdef MALLOCLOG
372 1.27 thorpej hitmlog(va);
373 1.27 thorpej #endif
374 1.8 cgd break;
375 1.8 cgd }
376 1.11 cgd
377 1.8 cgd freep->spare0 = 0;
378 1.8 cgd #endif /* DIAGNOSTIC */
379 1.1 cgd #ifdef KMEMSTATS
380 1.1 cgd kup = btokup(va);
381 1.1 cgd if (kup->ku_indx != indx)
382 1.1 cgd panic("malloc: wrong bucket");
383 1.1 cgd if (kup->ku_freecnt == 0)
384 1.1 cgd panic("malloc: lost data");
385 1.1 cgd kup->ku_freecnt--;
386 1.1 cgd kbp->kb_totalfree--;
387 1.1 cgd ksp->ks_memuse += 1 << indx;
388 1.1 cgd out:
389 1.1 cgd kbp->kb_calls++;
390 1.1 cgd ksp->ks_inuse++;
391 1.1 cgd ksp->ks_calls++;
392 1.1 cgd if (ksp->ks_memuse > ksp->ks_maxused)
393 1.1 cgd ksp->ks_maxused = ksp->ks_memuse;
394 1.1 cgd #else
395 1.1 cgd out:
396 1.1 cgd #endif
397 1.27 thorpej #ifdef MALLOCLOG
398 1.27 thorpej domlog(va, size, type, 1, file, line);
399 1.27 thorpej #endif
400 1.1 cgd splx(s);
401 1.67 enami if ((flags & M_ZERO) != 0)
402 1.65 lukem memset(va, 0, size);
403 1.1 cgd return ((void *) va);
404 1.1 cgd }
405 1.1 cgd
406 1.1 cgd /*
407 1.1 cgd * Free a block of memory allocated by malloc.
408 1.1 cgd */
409 1.27 thorpej #ifdef MALLOCLOG
410 1.27 thorpej void
411 1.69 enami _free(void *addr, int type, const char *file, long line)
412 1.27 thorpej #else
413 1.1 cgd void
414 1.69 enami free(void *addr, int type)
415 1.27 thorpej #endif /* MALLOCLOG */
416 1.1 cgd {
417 1.50 augustss struct kmembuckets *kbp;
418 1.50 augustss struct kmemusage *kup;
419 1.50 augustss struct freelist *freep;
420 1.8 cgd long size;
421 1.8 cgd int s;
422 1.5 andrew #ifdef DIAGNOSTIC
423 1.8 cgd caddr_t cp;
424 1.11 cgd int32_t *end, *lp;
425 1.11 cgd long alloc, copysize;
426 1.5 andrew #endif
427 1.1 cgd #ifdef KMEMSTATS
428 1.50 augustss struct kmemstats *ksp = &kmemstats[type];
429 1.48 thorpej #endif
430 1.48 thorpej
431 1.62 thorpej #ifdef MALLOC_DEBUG
432 1.62 thorpej if (debug_free(addr, type))
433 1.62 thorpej return;
434 1.62 thorpej #endif
435 1.62 thorpej
436 1.48 thorpej #ifdef DIAGNOSTIC
437 1.48 thorpej /*
438 1.48 thorpej * Ensure that we're free'ing something that we could
439 1.48 thorpej * have allocated in the first place. That is, check
440 1.48 thorpej * to see that the address is within kmem_map.
441 1.48 thorpej */
442 1.51 thorpej if (__predict_false((vaddr_t)addr < kmem_map->header.start ||
443 1.69 enami (vaddr_t)addr >= kmem_map->header.end))
444 1.48 thorpej panic("free: addr %p not within kmem_map", addr);
445 1.1 cgd #endif
446 1.1 cgd
447 1.1 cgd kup = btokup(addr);
448 1.1 cgd size = 1 << kup->ku_indx;
449 1.8 cgd kbp = &bucket[kup->ku_indx];
450 1.56 thorpej s = splvm();
451 1.27 thorpej #ifdef MALLOCLOG
452 1.27 thorpej domlog(addr, 0, type, 2, file, line);
453 1.27 thorpej #endif
454 1.1 cgd #ifdef DIAGNOSTIC
455 1.8 cgd /*
456 1.8 cgd * Check for returns of data that do not point to the
457 1.8 cgd * beginning of the allocation.
458 1.8 cgd */
459 1.49 thorpej if (size > PAGE_SIZE)
460 1.49 thorpej alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
461 1.1 cgd else
462 1.1 cgd alloc = addrmask[kup->ku_indx];
463 1.8 cgd if (((u_long)addr & alloc) != 0)
464 1.15 christos panic("free: unaligned addr %p, size %ld, type %s, mask %ld\n",
465 1.69 enami addr, size, memname[type], alloc);
466 1.1 cgd #endif /* DIAGNOSTIC */
467 1.1 cgd if (size > MAXALLOCSAVE) {
468 1.35 eeh uvm_km_free(kmem_map, (vaddr_t)addr, ctob(kup->ku_pagecnt));
469 1.1 cgd #ifdef KMEMSTATS
470 1.1 cgd size = kup->ku_pagecnt << PGSHIFT;
471 1.1 cgd ksp->ks_memuse -= size;
472 1.1 cgd kup->ku_indx = 0;
473 1.1 cgd kup->ku_pagecnt = 0;
474 1.1 cgd if (ksp->ks_memuse + size >= ksp->ks_limit &&
475 1.1 cgd ksp->ks_memuse < ksp->ks_limit)
476 1.1 cgd wakeup((caddr_t)ksp);
477 1.1 cgd ksp->ks_inuse--;
478 1.1 cgd kbp->kb_total -= 1;
479 1.1 cgd #endif
480 1.1 cgd splx(s);
481 1.1 cgd return;
482 1.1 cgd }
483 1.8 cgd freep = (struct freelist *)addr;
484 1.8 cgd #ifdef DIAGNOSTIC
485 1.8 cgd /*
486 1.8 cgd * Check for multiple frees. Use a quick check to see if
487 1.8 cgd * it looks free before laboriously searching the freelist.
488 1.8 cgd */
489 1.51 thorpej if (__predict_false(freep->spare0 == WEIRD_ADDR)) {
490 1.16 cgd for (cp = kbp->kb_next; cp;
491 1.16 cgd cp = ((struct freelist *)cp)->next) {
492 1.8 cgd if (addr != cp)
493 1.8 cgd continue;
494 1.22 christos printf("multiply freed item %p\n", addr);
495 1.27 thorpej #ifdef MALLOCLOG
496 1.27 thorpej hitmlog(addr);
497 1.27 thorpej #endif
498 1.8 cgd panic("free: duplicated free");
499 1.8 cgd }
500 1.8 cgd }
501 1.38 chs #ifdef LOCKDEBUG
502 1.38 chs /*
503 1.38 chs * Check if we're freeing a locked simple lock.
504 1.38 chs */
505 1.40 chs simple_lock_freecheck(addr, (char *)addr + size);
506 1.38 chs #endif
507 1.8 cgd /*
508 1.8 cgd * Copy in known text to detect modification after freeing
509 1.8 cgd * and to make it look free. Also, save the type being freed
510 1.8 cgd * so we can list likely culprit if modification is detected
511 1.8 cgd * when the object is reallocated.
512 1.8 cgd */
513 1.8 cgd copysize = size < MAX_COPY ? size : MAX_COPY;
514 1.11 cgd end = (int32_t *)&((caddr_t)addr)[copysize];
515 1.11 cgd for (lp = (int32_t *)addr; lp < end; lp++)
516 1.8 cgd *lp = WEIRD_ADDR;
517 1.8 cgd freep->type = type;
518 1.8 cgd #endif /* DIAGNOSTIC */
519 1.1 cgd #ifdef KMEMSTATS
520 1.1 cgd kup->ku_freecnt++;
521 1.36 thorpej if (kup->ku_freecnt >= kbp->kb_elmpercl) {
522 1.1 cgd if (kup->ku_freecnt > kbp->kb_elmpercl)
523 1.1 cgd panic("free: multiple frees");
524 1.1 cgd else if (kbp->kb_totalfree > kbp->kb_highwat)
525 1.1 cgd kbp->kb_couldfree++;
526 1.36 thorpej }
527 1.1 cgd kbp->kb_totalfree++;
528 1.1 cgd ksp->ks_memuse -= size;
529 1.1 cgd if (ksp->ks_memuse + size >= ksp->ks_limit &&
530 1.1 cgd ksp->ks_memuse < ksp->ks_limit)
531 1.1 cgd wakeup((caddr_t)ksp);
532 1.1 cgd ksp->ks_inuse--;
533 1.1 cgd #endif
534 1.8 cgd if (kbp->kb_next == NULL)
535 1.8 cgd kbp->kb_next = addr;
536 1.8 cgd else
537 1.8 cgd ((struct freelist *)kbp->kb_last)->next = addr;
538 1.8 cgd freep->next = NULL;
539 1.8 cgd kbp->kb_last = addr;
540 1.1 cgd splx(s);
541 1.20 cgd }
542 1.20 cgd
543 1.20 cgd /*
544 1.20 cgd * Change the size of a block of memory.
545 1.20 cgd */
546 1.20 cgd void *
547 1.69 enami realloc(void *curaddr, unsigned long newsize, int type, int flags)
548 1.20 cgd {
549 1.50 augustss struct kmemusage *kup;
550 1.72 thorpej unsigned long cursize;
551 1.20 cgd void *newaddr;
552 1.20 cgd #ifdef DIAGNOSTIC
553 1.20 cgd long alloc;
554 1.20 cgd #endif
555 1.20 cgd
556 1.20 cgd /*
557 1.69 enami * realloc() with a NULL pointer is the same as malloc().
558 1.20 cgd */
559 1.20 cgd if (curaddr == NULL)
560 1.20 cgd return (malloc(newsize, type, flags));
561 1.20 cgd
562 1.20 cgd /*
563 1.69 enami * realloc() with zero size is the same as free().
564 1.20 cgd */
565 1.20 cgd if (newsize == 0) {
566 1.20 cgd free(curaddr, type);
567 1.20 cgd return (NULL);
568 1.20 cgd }
569 1.59 thorpej
570 1.59 thorpej #ifdef LOCKDEBUG
571 1.59 thorpej if ((flags & M_NOWAIT) == 0)
572 1.59 thorpej simple_lock_only_held(NULL, "realloc");
573 1.59 thorpej #endif
574 1.20 cgd
575 1.20 cgd /*
576 1.20 cgd * Find out how large the old allocation was (and do some
577 1.20 cgd * sanity checking).
578 1.20 cgd */
579 1.20 cgd kup = btokup(curaddr);
580 1.20 cgd cursize = 1 << kup->ku_indx;
581 1.20 cgd
582 1.20 cgd #ifdef DIAGNOSTIC
583 1.20 cgd /*
584 1.20 cgd * Check for returns of data that do not point to the
585 1.20 cgd * beginning of the allocation.
586 1.20 cgd */
587 1.49 thorpej if (cursize > PAGE_SIZE)
588 1.49 thorpej alloc = addrmask[BUCKETINDX(PAGE_SIZE)];
589 1.20 cgd else
590 1.20 cgd alloc = addrmask[kup->ku_indx];
591 1.20 cgd if (((u_long)curaddr & alloc) != 0)
592 1.69 enami panic("realloc: "
593 1.69 enami "unaligned addr %p, size %ld, type %s, mask %ld\n",
594 1.69 enami curaddr, cursize, memname[type], alloc);
595 1.20 cgd #endif /* DIAGNOSTIC */
596 1.20 cgd
597 1.20 cgd if (cursize > MAXALLOCSAVE)
598 1.20 cgd cursize = ctob(kup->ku_pagecnt);
599 1.20 cgd
600 1.20 cgd /*
601 1.20 cgd * If we already actually have as much as they want, we're done.
602 1.20 cgd */
603 1.20 cgd if (newsize <= cursize)
604 1.20 cgd return (curaddr);
605 1.20 cgd
606 1.20 cgd /*
607 1.20 cgd * Can't satisfy the allocation with the existing block.
608 1.20 cgd * Allocate a new one and copy the data.
609 1.20 cgd */
610 1.20 cgd newaddr = malloc(newsize, type, flags);
611 1.51 thorpej if (__predict_false(newaddr == NULL)) {
612 1.20 cgd /*
613 1.69 enami * malloc() failed, because flags included M_NOWAIT.
614 1.20 cgd * Return NULL to indicate that failure. The old
615 1.20 cgd * pointer is still valid.
616 1.20 cgd */
617 1.69 enami return (NULL);
618 1.20 cgd }
619 1.34 perry memcpy(newaddr, curaddr, cursize);
620 1.20 cgd
621 1.20 cgd /*
622 1.20 cgd * We were successful: free the old allocation and return
623 1.20 cgd * the new one.
624 1.20 cgd */
625 1.20 cgd free(curaddr, type);
626 1.20 cgd return (newaddr);
627 1.70 enami }
628 1.70 enami
629 1.70 enami /*
630 1.70 enami * Roundup size to the actual allocation size.
631 1.70 enami */
632 1.70 enami unsigned long
633 1.70 enami malloc_roundup(unsigned long size)
634 1.70 enami {
635 1.70 enami
636 1.70 enami if (size > MAXALLOCSAVE)
637 1.70 enami return (roundup(size, PAGE_SIZE));
638 1.70 enami else
639 1.70 enami return (1 << BUCKETINDX(size));
640 1.1 cgd }
641 1.1 cgd
642 1.1 cgd /*
643 1.49 thorpej * Compute the number of pages that kmem_map will map, that is,
644 1.49 thorpej * the size of the kernel malloc arena.
645 1.49 thorpej */
646 1.49 thorpej void
647 1.69 enami kmeminit_nkmempages(void)
648 1.49 thorpej {
649 1.49 thorpej int npages;
650 1.49 thorpej
651 1.49 thorpej if (nkmempages != 0) {
652 1.49 thorpej /*
653 1.49 thorpej * It's already been set (by us being here before, or
654 1.49 thorpej * by patching or kernel config options), bail out now.
655 1.49 thorpej */
656 1.49 thorpej return;
657 1.49 thorpej }
658 1.49 thorpej
659 1.49 thorpej /*
660 1.49 thorpej * We use the following (simple) formula:
661 1.49 thorpej *
662 1.49 thorpej * - Starting point is physical memory / 4.
663 1.49 thorpej *
664 1.49 thorpej * - Clamp it down to NKMEMPAGES_MAX.
665 1.49 thorpej *
666 1.49 thorpej * - Round it up to NKMEMPAGES_MIN.
667 1.49 thorpej */
668 1.49 thorpej npages = physmem / 4;
669 1.49 thorpej
670 1.49 thorpej if (npages > NKMEMPAGES_MAX)
671 1.49 thorpej npages = NKMEMPAGES_MAX;
672 1.49 thorpej
673 1.49 thorpej if (npages < NKMEMPAGES_MIN)
674 1.49 thorpej npages = NKMEMPAGES_MIN;
675 1.49 thorpej
676 1.49 thorpej nkmempages = npages;
677 1.49 thorpej }
678 1.49 thorpej
679 1.49 thorpej /*
680 1.1 cgd * Initialize the kernel memory allocator
681 1.1 cgd */
682 1.12 christos void
683 1.69 enami kmeminit(void)
684 1.1 cgd {
685 1.23 tls #ifdef KMEMSTATS
686 1.50 augustss long indx;
687 1.23 tls #endif
688 1.1 cgd
689 1.1 cgd #if ((MAXALLOCSAVE & (MAXALLOCSAVE - 1)) != 0)
690 1.1 cgd ERROR!_kmeminit:_MAXALLOCSAVE_not_power_of_2
691 1.1 cgd #endif
692 1.1 cgd #if (MAXALLOCSAVE > MINALLOCSIZE * 32768)
693 1.1 cgd ERROR!_kmeminit:_MAXALLOCSAVE_too_big
694 1.1 cgd #endif
695 1.47 ragge #if (MAXALLOCSAVE < NBPG)
696 1.1 cgd ERROR!_kmeminit:_MAXALLOCSAVE_too_small
697 1.1 cgd #endif
698 1.11 cgd
699 1.11 cgd if (sizeof(struct freelist) > (1 << MINBUCKET))
700 1.11 cgd panic("minbucket too small/struct freelist too big");
701 1.11 cgd
702 1.49 thorpej /*
703 1.49 thorpej * Compute the number of kmem_map pages, if we have not
704 1.49 thorpej * done so already.
705 1.49 thorpej */
706 1.49 thorpej kmeminit_nkmempages();
707 1.49 thorpej
708 1.28 mrg kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map,
709 1.69 enami (vsize_t)(nkmempages * sizeof(struct kmemusage)));
710 1.35 eeh kmem_map = uvm_km_suballoc(kernel_map, (vaddr_t *)&kmembase,
711 1.69 enami (vaddr_t *)&kmemlimit, (vsize_t)(nkmempages << PAGE_SHIFT),
712 1.69 enami VM_MAP_INTRSAFE, FALSE, &kmem_map_store);
713 1.1 cgd #ifdef KMEMSTATS
714 1.1 cgd for (indx = 0; indx < MINBUCKET + 16; indx++) {
715 1.49 thorpej if (1 << indx >= PAGE_SIZE)
716 1.1 cgd bucket[indx].kb_elmpercl = 1;
717 1.1 cgd else
718 1.49 thorpej bucket[indx].kb_elmpercl = PAGE_SIZE / (1 << indx);
719 1.1 cgd bucket[indx].kb_highwat = 5 * bucket[indx].kb_elmpercl;
720 1.1 cgd }
721 1.8 cgd for (indx = 0; indx < M_LAST; indx++)
722 1.60 thorpej kmemstats[indx].ks_limit =
723 1.60 thorpej ((u_long)nkmempages << PAGE_SHIFT) * 6U / 10U;
724 1.62 thorpej #endif
725 1.62 thorpej #ifdef MALLOC_DEBUG
726 1.62 thorpej debug_malloc_init();
727 1.1 cgd #endif
728 1.1 cgd }
729 1.39 thorpej
730 1.39 thorpej #ifdef DDB
731 1.39 thorpej #include <ddb/db_output.h>
732 1.39 thorpej
733 1.39 thorpej /*
734 1.39 thorpej * Dump kmem statistics from ddb.
735 1.39 thorpej *
736 1.39 thorpej * usage: call dump_kmemstats
737 1.39 thorpej */
738 1.69 enami void dump_kmemstats(void);
739 1.39 thorpej
740 1.39 thorpej void
741 1.69 enami dump_kmemstats(void)
742 1.39 thorpej {
743 1.39 thorpej #ifdef KMEMSTATS
744 1.39 thorpej const char *name;
745 1.39 thorpej int i;
746 1.39 thorpej
747 1.39 thorpej for (i = 0; i < M_LAST; i++) {
748 1.39 thorpej name = memname[i] ? memname[i] : "";
749 1.39 thorpej
750 1.39 thorpej db_printf("%2d %s%.*s %ld\n", i, name,
751 1.39 thorpej (int)(20 - strlen(name)), " ",
752 1.39 thorpej kmemstats[i].ks_memuse);
753 1.39 thorpej }
754 1.39 thorpej #else
755 1.39 thorpej db_printf("Kmem stats are not being collected.\n");
756 1.39 thorpej #endif /* KMEMSTATS */
757 1.39 thorpej }
758 1.39 thorpej #endif /* DDB */
759