share/doc/papers/kernmalloc/appendix.ms

   1 .\" $FreeBSD$
   2 .am vS
   3 ..
   4 .am vE
   5 ..
   6 'ss 23
   7 'ds _ \d\(mi\u
   8 'ps 9z
   9 'vs 10p
  10 'ds - \(mi
  11 'ds / \\h'\\w' 'u-\\w'/'u'/
  12 'ds /* \\h'\\w' 'u-\\w'/'u'/*
  13 'bd B 3
  14 'bd S B 3
  15 'nr cm 0
  16 'nf
  17 'de vH
  18 'ev 2
  19 'ft 1
  20 'sp .35i
  21 'tl '\s14\f3\\*(=F\fP\s0'\\*(=H'\f3\s14\\*(=F\fP\s0'
  22 'sp .25i
  23 'ft 1
  24 \f2\s12\h'\\n(.lu-\w'\\*(=f'u'\\*(=f\fP\s0\h'|0u'
  25 .sp .05i
  26 'ev
  27 'ds =G \\*(=F
  28 ..
  29 'de vF
  30 'ev 2
  31 'sp .35i
  32 'ie o 'tl '\f2\\*(=M''Page % of \\*(=G\fP'
  33 'el 'tl '\f2Page % of \\*(=G''\\*(=M\fP'
  34 'bp
  35 'ev
  36 'ft 1
  37 'if \\n(cm=1 'ft 2
  38 ..
  39 'de ()
  40 'pn 1
  41 ..
  42 'de +C
  43 'nr cm 1
  44 'ft 2
  45 'ds +K
  46 'ds -K
  47 ..
  48 'de -C
  49 'nr cm 0
  50 'ft 1
  51 'ds +K \f3
  52 'ds -K \fP
  53 ..
  54 '+C
  55 '-C
  56 'am +C
  57 'ne 3
  58 ..
  59 'de FN
  60 \f2\s14\h'\\n(.lu-\w'\\$1'u'\\$1\fP\s0\h'|0u'\c
  61 .if r x .if \\nx .if d =F .tm \\$1 \\*(=F \\n%
  62 'ds =f \&...\\$1
  63 ..
  64 'de FC
  65 .if r x .if \\nx .if d =F .tm \\$1 \\*(=F \\n%
  66 'ds =f \&...\\$1
  67 ..
  68 'de -F
  69 'rm =f
  70 ..
  71 'ft 1
  72 'lg 0
  73 '-F
  74 .\" Copyright (c) 1988 The Regents of the University of California.
  75 .\" All rights reserved.
  76 .\"
  77 .\" Redistribution and use in source and binary forms, with or without
  78 .\" modification, are permitted provided that the following conditions
  79 .\" are met:
  80 .\" 1. Redistributions of source code must retain the above copyright
  81 .\"    notice, this list of conditions and the following disclaimer.
  82 .\" 2. Redistributions in binary form must reproduce the above copyright
  83 .\"    notice, this list of conditions and the following disclaimer in the
  84 .\"    documentation and/or other materials provided with the distribution.
  85 .\" 3. All advertising materials mentioning features or use of this software
  86 .\"    must display the following acknowledgement:
  87 .\"     This product includes software developed by the University of
  88 .\"     California, Berkeley and its contributors.
  89 .\" 4. Neither the name of the University nor the names of its contributors
  90 .\"    may be used to endorse or promote products derived from this software
  91 .\"    without specific prior written permission.
  92 .\"
  93 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  94 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  95 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  96 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  97 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  98 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  99 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 100 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 101 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 102 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 103 .\" SUCH DAMAGE.
 104 .\"
 105 .\"     @(#)appendix.t  5.1 (Berkeley) 4/16/91
 106 .\"
 107 .bp
 108 .H 1 "Appendix A - Implementation Details"
 109 .LP
 110 .nf
 111 .vS
 112 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 113 '+C
 114
 115  \fI*\fP Constants for setting the parameters of the kernel memory allocator\&.
 116  \fI*\fP
 117  \fI*\fP 2 \fI*\fP\fI*\fP MINBUCKET is the smallest unit of memory that will be
 118  \fI*\fP allocated\&. It must be at least large enough to hold a pointer\&.
 119  \fI*\fP
 120  \fI*\fP Units of memory less or equal to MAXALLOCSAVE will permanently
 121  \fI*\fP allocate physical memory; requests for these size pieces of memory
 122  \fI*\fP are quite fast\&. Allocations greater than MAXALLOCSAVE must
 123  \fI*\fP always allocate and free physical memory; requests for these size
 124  \fI*\fP allocations should be done infrequently as they will be slow\&.
 125  \fI*\fP Constraints: CLBYTES <= MAXALLOCSAVE <= 2 \fI*\fP\fI*\fP (MINBUCKET + 14)
 126  \fI*\fP and MAXALLOCSIZE must be a power of two\&.
 127  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 128 '-C
 129
 130 \*(+K#define\*(-K MINBUCKET\h'|31n'4\h'|51n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 131 '+C
 132  4 => min allocation of 16 bytes \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 133 '-C
 134
 135 'FN MAXALLOCSAVE
 136 \*(+K#define\*(-K MAXALLOCSAVE\h'|31n'(2 \fI*\fP CLBYTES)
 137
 138 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 139 '+C
 140
 141  \fI*\fP Maximum amount of kernel dynamic memory\&.
 142  \fI*\fP Constraints: must be a multiple of the pagesize\&.
 143  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 144 '-C
 145
 146 'FN MAXKMEM
 147 \*(+K#define\*(-K MAXKMEM\h'|31n'(1024 \fI*\fP PAGESIZE)
 148
 149 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 150 '+C
 151
 152  \fI*\fP Arena for all kernel dynamic memory allocation\&.
 153  \fI*\fP This arena is known to start on a page boundary\&.
 154  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 155 '-C
 156
 157 \*(+Kextern\*(-K \*(+Kchar\*(-K kmembase[MAXKMEM];
 158
 159 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 160 '+C
 161
 162  \fI*\fP Array of descriptors that describe the contents of each page
 163  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 164 '-C
 165
 166 \*(+Kstruct\*(-K kmemsizes \*(+K{\*(-K
 167 \h'|11n'\*(+Kshort\*(-K\h'|21n'ks\*_indx;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 168 '+C
 169  bucket index, size of small allocations \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 170 '-C
 171
 172 \h'|11n'u\*_short\h'|21n'ks\*_pagecnt;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 173 '+C
 174  for large allocations, pages allocated \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 175 '-C
 176
 177 \*(+K}\*(-K\c\c
 178 '-F
 179  kmemsizes[MAXKMEM \fI\h'\w' 'u-\w'/'u'/\fP PAGESIZE];
 180 'FC MAXALLOCSAVE
 181
 182 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 183 '+C
 184
 185  \fI*\fP Set of buckets for each size of memory block that is retained
 186  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 187 '-C
 188
 189 \*(+Kstruct\*(-K kmembuckets \*(+K{\*(-K
 190 \h'|11n'caddr\*_t kb\*_next;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 191 '+C
 192  list of free blocks \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 193 '-C
 194
 195 \*(+K}\*(-K\c\c
 196 '-F
 197  bucket[MINBUCKET + 16];
 198 .bp
 199 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 200 '+C
 201
 202  \fI*\fP Macro to convert a size to a bucket index\&. If the size is constant,
 203  \fI*\fP this macro reduces to a compile time constant\&.
 204  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 205 '-C
 206
 207 'FN MINALLOCSIZE
 208 \*(+K#define\*(-K MINALLOCSIZE\h'|31n'(1 << MINBUCKET)
 209 'FN BUCKETINDX
 210 \*(+K#define\*(-K BUCKETINDX(size) \e
 211 \h'|11n'(size) <= (MINALLOCSIZE \fI*\fP 128) \e
 212 \h'|21n'? (size) <= (MINALLOCSIZE \fI*\fP 8) \e
 213 \h'|31n'? (size) <= (MINALLOCSIZE \fI*\fP 2) \e
 214 \h'|41n'? (size) <= (MINALLOCSIZE \fI*\fP 1) \e
 215 \h'|51n'? (MINBUCKET + 0) \e
 216 \h'|51n': (MINBUCKET + 1) \e
 217 \h'|41n': (size) <= (MINALLOCSIZE \fI*\fP 4) \e
 218 \h'|51n'? (MINBUCKET + 2) \e
 219 \h'|51n': (MINBUCKET + 3) \e
 220 \h'|31n': (size) <= (MINALLOCSIZE\fI*\fP 32) \e
 221 \h'|41n'? (size) <= (MINALLOCSIZE \fI*\fP 16) \e
 222 \h'|51n'? (MINBUCKET + 4) \e
 223 \h'|51n': (MINBUCKET + 5) \e
 224 \h'|41n': (size) <= (MINALLOCSIZE \fI*\fP 64) \e
 225 \h'|51n'? (MINBUCKET + 6) \e
 226 \h'|51n': (MINBUCKET + 7) \e
 227 \h'|21n': (size) <= (MINALLOCSIZE \fI*\fP 2048) \e
 228 \h'|31n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 229 '+C
 230  etc \&.\&.\&. \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 231 '-C
 232
 233
 234 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 235 '+C
 236
 237  \fI*\fP Macro versions for the usual cases of malloc\fI\h'\w' 'u-\w'/'u'/\fPfree
 238  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 239 '-C
 240
 241 'FN MALLOC
 242 \*(+K#define\*(-K MALLOC(space, cast, size, flags) \*(+K{\*(-K \e
 243 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmembuckets \fI*\fPkbp = &bucket[BUCKETINDX(size)]; \e
 244 \h'|11n'\*(+Klong\*(-K s = splimp(); \e
 245 \h'|11n'\*(+Kif\*(-K (kbp\*->kb\*_next == NULL) \*(+K{\*(-K \e
 246 \h'|21n'(space) = (cast)malloc(size, flags); \e
 247 \h'|11n'\*(+K}\*(-K \*(+Kelse\*(-K \*(+K{\*(-K \e
 248 \h'|21n'(space) = (cast)kbp\*->kb\*_next; \e
 249 \h'|21n'kbp\*->kb\*_next = \fI*\fP(caddr\*_t \fI*\fP)(space); \e
 250 \h'|11n'\*(+K}\*(-K \e
 251 \h'|11n'splx(s); \e
 252 \*(+K}\*(-K\c\c
 253 '-F
 254
 255 'FC BUCKETINDX
 256
 257 'FN FREE
 258 \*(+K#define\*(-K FREE(addr) \*(+K{\*(-K \e
 259 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmembuckets \fI*\fPkbp; \e
 260 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmemsizes \fI*\fPksp = \e
 261 \h'|21n'&kmemsizes[((addr) \*- kmembase) \fI\h'\w' 'u-\w'/'u'/\fP PAGESIZE]; \e
 262 \h'|11n'\*(+Klong\*(-K s = splimp(); \e
 263 \h'|11n'\*(+Kif\*(-K (1 << ksp\*->ks\*_indx > MAXALLOCSAVE) \*(+K{\*(-K \e
 264 \h'|21n'free(addr); \e
 265 \h'|11n'\*(+K}\*(-K \*(+Kelse\*(-K \*(+K{\*(-K \e
 266 \h'|21n'kbp = &bucket[ksp\*->ks\*_indx]; \e
 267 \h'|21n'\fI*\fP(caddr\*_t \fI*\fP)(addr) = kbp\*->kb\*_next; \e
 268 \h'|21n'kbp\*->kb\*_next = (caddr\*_t)(addr); \e
 269 \h'|11n'\*(+K}\*(-K \e
 270 \h'|11n'splx(s); \e
 271 \*(+K}\*(-K\c\c
 272 '-F
 273
 274 'FC BUCKETINDX
 275 .vE