Branch
Hash :
1a08f436
Author :
Date :
2010-08-25T09:23:17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
\ ========== Copyright Header Begin ==========================================
\
\ Hypervisor Software File: malloc.fth
\
\ Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
\
\ - Do no alter or remove copyright notices
\
\ - Redistribution and use of this software in source and binary forms, with
\ or without modification, are permitted provided that the following
\ conditions are met:
\
\ - Redistribution of source code must retain the above copyright notice,
\ this list of conditions and the following disclaimer.
\
\ - Redistribution in binary form must reproduce the above copyright notice,
\ this list of conditions and the following disclaimer in the
\ documentation and/or other materials provided with the distribution.
\
\ Neither the name of Sun Microsystems, Inc. or the names of contributors
\ may be used to endorse or promote products derived from this software
\ without specific prior written permission.
\
\ This software is provided "AS IS," without a warranty of any kind.
\ ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
\ INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
\ PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
\ MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
\ ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
\ DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN
\ OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR
\ FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
\ DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
\ ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
\ SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
\
\ You acknowledge that this software is not designed, licensed or
\ intended for use in the design, construction, operation or maintenance of
\ any nuclear facility.
\
\ ========== Copyright Header End ============================================
id: @(#)malloc.fth 2.10 03/09/09
purpose:
copyright: Copyright 1990-2001, 2003 Sun Microsystems, Inc. All Rights Reserved
\ Forth dynamic storage managment.
\
\ By Don Hopkins, University of Maryland
\ Modified by Mitch Bradley, Bradley Forthware
\ Public Domain
\
\ First fit storage allocation of blocks of varying size.
\ Blocks are prefixed with a usage flag and a length count.
\ Free blocks are collapsed downwards during free-memory and while
\ searching during allocate-memory. Based on the algorithm described
\ in Knuth's _An_Introduction_To_Data_Structures_With_Applications_,
\ sections 5-6.2 and 5-6.3, pp. 501-511.
\
\ init-allocator ( -- )
\ Initializes the allocator, with no memory. Should be executed once,
\ before any other allocation operations are attempted.
\
\ add-memory ( adr len -- )
\ Adds a region of memory to the allocation pool. That memory will
\ be available for subsequent use by allocate-memory. This may
\ be executed any number of times.
\
\ allocate-memory ( size -- adr false | error true )
\ Tries to allocate a chunk of memory at least size bytes long.
\ Returns error code and true on failure, or the address of the
\ first byte of usable data and false on success.
\
\ free-memory ( adr -- )
\ Frees a chunk of memory allocated by malloc. adr should be an
\ address returned by allocate-memory. Error if adr is not a
\ valid address.
\
\ memory-available ( -- size )
\ Returns the size in bytes of the largest contiguous chunk of memory
\ that can be allocated by allocate-memory .
headers
vocabulary allocator
also allocator also definitions
headerless
8 constant #dalign \ Machine-dependent worst-case alignment boundary
2 base !
1110000000000111 constant *dbuf-free*
1111010101011111 constant *dbuf-used*
decimal
\ : field \ name ( offset size -- offset' )
\ create over , + does> @ +
\ ;
struct
/n field >dbuf-flag
/n field >dbuf-size
aligned
0 field >dbuf-data
/n field >dbuf-suc
/n field >dbuf-pred
constant dbuf-min
\ In a multitasking system, the memory allocator head node should
\ be located in a global area, instead in the per-task user area.
dbuf-min ualloc user dbuf-head
: dbuf-data> ( adr -- 'dbuf ) 0 >dbuf-data - ;
: dbuf-flag! ( flag 'dbuf -- ) >dbuf-flag ! ;
: dbuf-flag@ ( 'dbuf -- flag ) >dbuf-flag @ ;
: dbuf-size! ( size 'dbuf -- ) >dbuf-size ! ;
: dbuf-size@ ( 'dbuf -- size ) >dbuf-size @ ;
: dbuf-suc! ( suc 'dbuf -- ) >dbuf-suc ! ;
: dbuf-suc@ ( 'dbuf -- 'dbuf ) >dbuf-suc @ ;
: dbuf-pred! ( pred 'dbuf -- ) >dbuf-pred ! ;
: dbuf-pred@ ( 'dbuf -- 'dbuf ) >dbuf-pred @ ;
: next-dbuf ( 'dbuf -- 'next-dbuf ) dup dbuf-size@ + ;
\ Insert new-node into doubly-linked list after old-node
: insert-after ( new-node old-node -- )
>r r@ dbuf-suc@ over dbuf-suc! \ old's suc is now new's suc
dup r@ dbuf-suc! \ new is now old's suc
r> over dbuf-pred! \ old is now new's pred
dup dbuf-suc@ dbuf-pred! \ new is now new's suc's pred
;
: link-with-free ( 'dbuf -- )
\ Following code will look for possibility of this node getting
\ merged with any of the other nodes. If it cannot be merged than
\ create a new node and mark it as "free". The algorithm is to
\ start with the "head" node and look for "next-dbuf" of the first
\ node if it's free node and see if it matches with the start address
\ of the current node. If it does, then just add this node's "size" to
\ the node. If this can not be merged or the dbuf is not free then
\ continue search with the next dbuf until we go through all the nodes.
dbuf-head dbuf-suc@ ( 'dbuf head-suc )
begin ( 'dbuf dbuf-suc )
dup dbuf-head = if ( 'dbuf dbuf-suc )
drop ( 'dbuf )
*dbuf-free* over dbuf-flag! \ Set node status to "free"
dbuf-head insert-after \ Insert in list after head node
exit
else ( 'dbuf dbuf-suc )
dup dbuf-flag@ *dbuf-free* = if ( 'dbuf dbuf-suc )
over >r ( 'dbuf dbuf-suc ) ( r: 'dbuf )
dup next-dbuf ( 'dbuf dbuf-suc next-dbuf ) ( r: 'dbuf )
rot ( dbuf-suc next-dbuf 'dbuf ) ( r: 'dbuf )
= if ( dbuf-suc ) ( r: 'debuf )
r> dbuf-size@ ( dbuf-suc dbuf-size )
over dbuf-size@ + ( dbuf-suc dbuf-new-size )
swap dbuf-size! ( ) \ Found node to link, just add the size
true ( true )
else ( dbuf-suc ) ( r: 'dbuf )
dbuf-suc@ r> ( dbuf-suc 'dbuf )
swap false ( 'dbuf dbuf-suc false )
then
else ( 'dbuf dbuf-suc )
dbuf-suc@ ( 'dbuf dbuf-suc )
false ( 'dbuf dbuf-suc false )
then
then
until
;
\ Remove node from doubly-linked list
: remove-node ( node -- )
dup dbuf-pred@ over dbuf-suc@ dbuf-pred!
dup dbuf-suc@ swap dbuf-pred@ dbuf-suc!
;
\ Collapse the next node into the current node
: merge-with-next ( 'dbuf -- )
dup next-dbuf dup remove-node ( 'dbuf >next-dbuf ) \ Off of free list
over dbuf-size@ swap dbuf-size@ + rot dbuf-size! \ Increase size
;
\ 'dbuf is a free node. Merge all free nodes immediately following
\ into the node.
: merge-down ( 'dbuf -- 'dbuf )
begin
dup next-dbuf dbuf-flag@ *dbuf-free* =
while
dup merge-with-next
repeat
;
: .node ( 'dbuf -- )
base @ swap hex
dup 8 u.r 3 spaces
dup dbuf-flag@ 5 u.r
dup dbuf-size@ 9 u.r
dup dbuf-suc@ 9 u.r
dbuf-pred@ 9 u.r
cr
base !
;
headers
: .list ( -- )
dbuf-head
begin dbuf-suc@ dup dbuf-head <> while dup .node repeat
drop
;
headerless
forth definitions
: msize ( adr -- count ) dbuf-data> dbuf-size@ dbuf-data> ;
: free-memory ( adr -- )
dbuf-data> ( 'dbuf )
dup dbuf-flag@ *dbuf-used* - if
\ This is here because the the allocator has completely given up
\ and rather than corrupt state we just deliberately puke.
\ the old 'abort' was insufficient because it was being caught and the
\ error code mis-interpreted; so instead we force a hard fault that we
\ can back trace.
??cr ." FATAL: free-memory: bad address." cr -1 @
then
merge-down link-with-free
;
: add-memory ( adr len -- )
\ Align the starting address to a "worst-case" boundary. This helps
\ guarantee that allocated data areas will be on a "worst-case"
\ alignment boundary.
swap dup #dalign round-up ( len adr adr' )
dup rot - ( len adr' diff )
rot swap - ( adr' len' )
#dalign round-down ( adr' len'' )
\ Set size and flags fields for first piece
\ Subtract off the size of one node header, because we carve out
\ a node header from the end of the piece to use as a "stopper".
\ That "stopper" is marked "used", and prevents merge-down from
\ trying to merge past the end of the piece.
dbuf-data> ( 'dbuf-first #dbuf-first )
\ Ensure that the piece is big enough to be useable.
\ A piece of size dbuf-min (after having subtracted off the "stopper"
\ header) is barely useable, because the space used by the free list
\ links can be used as the data space.
dup dbuf-min < abort" add-memory: piece too small"
\ Set the size and flag for the new free piece
*dbuf-free* 2 pick dbuf-flag! ( 'dbuf-first #dbuf-first )
2dup swap dbuf-size! ( 'dbuf-first #dbuf-first )
\ Create the "stopper" header
\ XXX The stopper piece should be linked into a piece list,
\ and the flags should be set to a different value. The size
\ field should indicate the total size for this piece.
\ The piece list should be consulted when adding memory, and
\ if there is a piece immediately following the new piece, they
\ should be merged.
over + ( 'dbuf-first 'dbuf-limit )
*dbuf-used* swap dbuf-flag! ( 'dbuf-first )
link-with-free
;
: (allocate-memory) ( size -- adr false | error-code true )
\ Keep pieces aligned on "worst-case" hardware boundaries
#dalign round-up ( size' )
>dbuf-data dbuf-min max ( size )
\ Search for a sufficiently-large free piece
dbuf-head ( size 'dbuf )
begin ( size 'dbuf )
dbuf-suc@ ( size 'dbuf )
dup dbuf-head = if \ Bail out if we've already been around
2drop 1 true exit ( error-code true )
then ( size 'dbuf-suc )
merge-down ( size 'dbuf )
dup dbuf-size@ ( size 'dbuf dbuf-size )
2 pick >= ( size 'dbuf big-enough? )
until ( size 'dbuf )
dup dbuf-size@ 2 pick - ( size 'dbuf left-over )
dup dbuf-min <= if \ Too small to fragment?
\ The piece is too small to split, so we just remove the whole
\ thing from the free list.
drop nip ( 'dbuf )
dup remove-node ( 'dbuf )
else ( size 'dbuf left-over )
\ The piece is big enough to split up, so we make the free piece
\ smaller and take the stuff after it as the allocated piece.
2dup swap dbuf-size! ( size 'dbuf left-over) \ Set frag size
+ ( size 'dbuf' )
tuck dbuf-size! ( 'dbuf' )
then
*dbuf-used* over dbuf-flag! \ Mark as used
>dbuf-data false ( adr false )
;
: memory-available ( -- size )
0 >dbuf-data ( current-largest-size )
dbuf-head ( size 'dbuf )
begin ( size 'dbuf )
dbuf-suc@ dup dbuf-head <> ( size 'dbuf more? )
while \ Go once around the free list
merge-down ( size 'dbuf )
dup dbuf-size@ ( size 'dbuf dbuf-size )
rot max swap ( size' 'dbuf )
repeat
drop dbuf-data> ( largest-data-size )
;
\ Head node has 0 size, is not free, and is initially linked to itself
: init-allocator ( -- )
*dbuf-used* dbuf-head dbuf-flag!
0 dbuf-head dbuf-size! \ Must be 0 so the allocator won't find it.
dbuf-head dup dbuf-suc! \ Link to self
dbuf-head dup dbuf-pred!
;
previous previous definitions
\ Tries to allocate, and if that fails, requests more memory from the system
also allocator also
defer more-memory ( request-size -- adr actual-size false | error-code true )
: allocate-memory ( size -- adr false | error-code true )
dup (allocate-memory) if ( size error-code )
\ No more memory in the heap; try to get some more from the system
drop ( size )
\ use same alignment requirements and add space
\ for header and stopper header as in (allocate-memory)
dup #dalign round-up ( size size' )
>dbuf-data >dbuf-data ( size size' )
more-memory if ( size error-code )
nip true ( error-code true )
else ( size adr actual )
add-memory ( size )
(allocate-memory) ( adr false | error-code true )
then ( adr false | error-code true )
else ( size adr )
nip false ( adr false )
then ( adr false | error-code true )
;
previous previous
: heap-alloc-mem ( bytes -- adr )
allocate-memory abort" Out of memory"
;
: heap-free-mem ( adr size -- ) drop free-memory ;
init-allocator
headers
h# 10.0000 constant 1meg