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. Neither the name of the University nor the names of its contributors
  86 .\"    may be used to endorse or promote products derived from this software
  87 .\"    without specific prior written permission.
  88 .\"
  89 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  90 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  91 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  92 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  93 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  94 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  95 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  96 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  97 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  98 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  99 .\" SUCH DAMAGE.
 100 .\"
 101 .\"     @(#)appendix.t  5.1 (Berkeley) 4/16/91
 102 .\"
 103 .bp
 104 .H 1 "Appendix A - Implementation Details"
 105 .LP
 106 .nf
 107 .vS
 108 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 109 '+C
 110
 111  \fI*\fP Constants for setting the parameters of the kernel memory allocator\&.
 112  \fI*\fP
 113  \fI*\fP 2 \fI*\fP\fI*\fP MINBUCKET is the smallest unit of memory that will be
 114  \fI*\fP allocated\&. It must be at least large enough to hold a pointer\&.
 115  \fI*\fP
 116  \fI*\fP Units of memory less or equal to MAXALLOCSAVE will permanently
 117  \fI*\fP allocate physical memory; requests for these size pieces of memory
 118  \fI*\fP are quite fast\&. Allocations greater than MAXALLOCSAVE must
 119  \fI*\fP always allocate and free physical memory; requests for these size
 120  \fI*\fP allocations should be done infrequently as they will be slow\&.
 121  \fI*\fP Constraints: CLBYTES <= MAXALLOCSAVE <= 2 \fI*\fP\fI*\fP (MINBUCKET + 14)
 122  \fI*\fP and MAXALLOCSIZE must be a power of two\&.
 123  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 124 '-C
 125
 126 \*(+K#define\*(-K MINBUCKET\h'|31n'4\h'|51n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 127 '+C
 128  4 => min allocation of 16 bytes \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 129 '-C
 130
 131 'FN MAXALLOCSAVE
 132 \*(+K#define\*(-K MAXALLOCSAVE\h'|31n'(2 \fI*\fP CLBYTES)
 133
 134 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 135 '+C
 136
 137  \fI*\fP Maximum amount of kernel dynamic memory\&.
 138  \fI*\fP Constraints: must be a multiple of the pagesize\&.
 139  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 140 '-C
 141
 142 'FN MAXKMEM
 143 \*(+K#define\*(-K MAXKMEM\h'|31n'(1024 \fI*\fP PAGESIZE)
 144
 145 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 146 '+C
 147
 148  \fI*\fP Arena for all kernel dynamic memory allocation\&.
 149  \fI*\fP This arena is known to start on a page boundary\&.
 150  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 151 '-C
 152
 153 \*(+Kextern\*(-K \*(+Kchar\*(-K kmembase[MAXKMEM];
 154
 155 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 156 '+C
 157
 158  \fI*\fP Array of descriptors that describe the contents of each page
 159  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 160 '-C
 161
 162 \*(+Kstruct\*(-K kmemsizes \*(+K{\*(-K
 163 \h'|11n'\*(+Kshort\*(-K\h'|21n'ks\*_indx;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 164 '+C
 165  bucket index, size of small allocations \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 166 '-C
 167
 168 \h'|11n'u\*_short\h'|21n'ks\*_pagecnt;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 169 '+C
 170  for large allocations, pages allocated \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 171 '-C
 172
 173 \*(+K}\*(-K\c\c
 174 '-F
 175  kmemsizes[MAXKMEM \fI\h'\w' 'u-\w'/'u'/\fP PAGESIZE];
 176 'FC MAXALLOCSAVE
 177
 178 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 179 '+C
 180
 181  \fI*\fP Set of buckets for each size of memory block that is retained
 182  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 183 '-C
 184
 185 \*(+Kstruct\*(-K kmembuckets \*(+K{\*(-K
 186 \h'|11n'caddr\*_t kb\*_next;\h'|41n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 187 '+C
 188  list of free blocks \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 189 '-C
 190
 191 \*(+K}\*(-K\c\c
 192 '-F
 193  bucket[MINBUCKET + 16];
 194 .bp
 195 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 196 '+C
 197
 198  \fI*\fP Macro to convert a size to a bucket index\&. If the size is constant,
 199  \fI*\fP this macro reduces to a compile time constant\&.
 200  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 201 '-C
 202
 203 'FN MINALLOCSIZE
 204 \*(+K#define\*(-K MINALLOCSIZE\h'|31n'(1 << MINBUCKET)
 205 'FN BUCKETINDX
 206 \*(+K#define\*(-K BUCKETINDX(size) \e
 207 \h'|11n'(size) <= (MINALLOCSIZE \fI*\fP 128) \e
 208 \h'|21n'? (size) <= (MINALLOCSIZE \fI*\fP 8) \e
 209 \h'|31n'? (size) <= (MINALLOCSIZE \fI*\fP 2) \e
 210 \h'|41n'? (size) <= (MINALLOCSIZE \fI*\fP 1) \e
 211 \h'|51n'? (MINBUCKET + 0) \e
 212 \h'|51n': (MINBUCKET + 1) \e
 213 \h'|41n': (size) <= (MINALLOCSIZE \fI*\fP 4) \e
 214 \h'|51n'? (MINBUCKET + 2) \e
 215 \h'|51n': (MINBUCKET + 3) \e
 216 \h'|31n': (size) <= (MINALLOCSIZE\fI*\fP 32) \e
 217 \h'|41n'? (size) <= (MINALLOCSIZE \fI*\fP 16) \e
 218 \h'|51n'? (MINBUCKET + 4) \e
 219 \h'|51n': (MINBUCKET + 5) \e
 220 \h'|41n': (size) <= (MINALLOCSIZE \fI*\fP 64) \e
 221 \h'|51n'? (MINBUCKET + 6) \e
 222 \h'|51n': (MINBUCKET + 7) \e
 223 \h'|21n': (size) <= (MINALLOCSIZE \fI*\fP 2048) \e
 224 \h'|31n'\fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 225 '+C
 226  etc \&.\&.\&. \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 227 '-C
 228
 229
 230 \fI\h'\w' 'u-\w'/'u'/\fP\fI*\fP\c\c
 231 '+C
 232
 233  \fI*\fP Macro versions for the usual cases of malloc\fI\h'\w' 'u-\w'/'u'/\fPfree
 234  \fI*\fP\fI\h'\w' 'u-\w'/'u'/\fP\c
 235 '-C
 236
 237 'FN MALLOC
 238 \*(+K#define\*(-K MALLOC(space, cast, size, flags) \*(+K{\*(-K \e
 239 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmembuckets \fI*\fPkbp = &bucket[BUCKETINDX(size)]; \e
 240 \h'|11n'\*(+Klong\*(-K s = splimp(); \e
 241 \h'|11n'\*(+Kif\*(-K (kbp\*->kb\*_next == NULL) \*(+K{\*(-K \e
 242 \h'|21n'(space) = (cast)malloc(size, flags); \e
 243 \h'|11n'\*(+K}\*(-K \*(+Kelse\*(-K \*(+K{\*(-K \e
 244 \h'|21n'(space) = (cast)kbp\*->kb\*_next; \e
 245 \h'|21n'kbp\*->kb\*_next = \fI*\fP(caddr\*_t \fI*\fP)(space); \e
 246 \h'|11n'\*(+K}\*(-K \e
 247 \h'|11n'splx(s); \e
 248 \*(+K}\*(-K\c\c
 249 '-F
 250
 251 'FC BUCKETINDX
 252
 253 'FN FREE
 254 \*(+K#define\*(-K FREE(addr) \*(+K{\*(-K \e
 255 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmembuckets \fI*\fPkbp; \e
 256 \h'|11n'\*(+Kregister\*(-K \*(+Kstruct\*(-K kmemsizes \fI*\fPksp = \e
 257 \h'|21n'&kmemsizes[((addr) \*- kmembase) \fI\h'\w' 'u-\w'/'u'/\fP PAGESIZE]; \e
 258 \h'|11n'\*(+Klong\*(-K s = splimp(); \e
 259 \h'|11n'\*(+Kif\*(-K (1 << ksp\*->ks\*_indx > MAXALLOCSAVE) \*(+K{\*(-K \e
 260 \h'|21n'free(addr); \e
 261 \h'|11n'\*(+K}\*(-K \*(+Kelse\*(-K \*(+K{\*(-K \e
 262 \h'|21n'kbp = &bucket[ksp\*->ks\*_indx]; \e
 263 \h'|21n'\fI*\fP(caddr\*_t \fI*\fP)(addr) = kbp\*->kb\*_next; \e
 264 \h'|21n'kbp\*->kb\*_next = (caddr\*_t)(addr); \e
 265 \h'|11n'\*(+K}\*(-K \e
 266 \h'|11n'splx(s); \e
 267 \*(+K}\*(-K\c\c
 268 '-F
 269
 270 'FC BUCKETINDX
 271 .vE