kernel/krl_incs/mem.inc

   1 ;----------------------------------------------------------;
   2 ; BOS kernel                Christoffer Bubach, 2003-2005. ;
   3 ;----------------------------------------------------------;
   4 ;                                                          ;
   5 ;           functions to allocate/free mem.                ;
   6 ;                                                          ;
   7 ;----------------------------------------------------------;
   8
   9 ;----------------;
  10 ;   variables    ;
  11 ;----------------;
  12       first_free     dd   0
  13       prev_pointer   dd   0
  14       size           dd   0
  15       next_pointer   dd   0
  16
  17
  18 ;------------------------------------------------------;
  19 ;   init mem                                           ;
  20 ;                   in: ebx = first free memory        ;
  21 ;                       ecx = total memory size        ;
  22 ;------------------------------------------------------;
  23 init_mem:
  24           push    ecx
  25
  26           mov     [first_free], ebx
  27           sub     ecx, ebx
  28           mov     [size], ecx
  29           mov     [prev_pointer], 0
  30           mov     [next_pointer], 0
  31           mov     ecx, [prev_pointer]
  32           mov     [ebx], ecx
  33           mov     ecx, [size]
  34           mov     [ebx+4], ecx
  35           mov     ecx, [next_pointer]
  36           mov     [ebx+8], ecx
  37
  38           pop     ecx
  39           ret
  40
  41
  42
  43 ;------------------------------------------------------;
  44 ;   allocate memory                                    ;
  45 ;                    in:  ebx = wanted size in bytes   ;
  46 ;                    out: eax = 0 if failed            ;
  47 ;                         ebx = pointer to memory      ;
  48 ;------------------------------------------------------;
  49 allocate_mem:
  50           push    ecx
  51           push    edx
  52
  53           mov     eax, [first_free]
  54
  55      .loop:
  56           mov     ecx, [eax]
  57           mov     [prev_pointer], ecx
  58
  59           mov     ecx, [eax+4]
  60           mov     [size], ecx
  61
  62           mov     ecx, [eax+8]
  63           mov     [next_pointer], ecx
  64
  65           cmp     [size], ebx
  66           jae     .found
  67           cmp     [next_pointer], 0
  68           je      .error
  69           mov     eax, [next_pointer]
  70           jmp     .loop
  71
  72      .error:
  73           xor     eax, eax
  74           jmp     .end
  75
  76      .found:
  77           mov     ecx, [size]
  78           sub     ecx, ebx
  79           jz      .equal
  80
  81           cmp     [next_pointer], 0
  82           jne     .next_exists
  83           cmp     [prev_pointer], 0
  84           jne     .prev_but_no_next
  85
  86
  87      ;----------------------------------------------;
  88      ; no other block exists; add new free block    ;
  89      ; with the reminding space as free, and move   ;
  90      ; "first free" to that block..                 ;
  91      ;----------------------------------------------;
  92           mov     ecx, eax                            ; move address to ecx and
  93           add     ecx, ebx                            ; add size. ecx=end requested
  94           mov     dword [ecx], 0                      ; set new header's prev to 0
  95           mov     edx, [size]
  96           sub     edx, ebx                            ; remaining space in edx
  97           mov     [ecx+4], edx                        ; save it to new header
  98           mov     dword [ecx+8], 0                    ; no next pointer..
  99
 100           mov     [first_free], ecx
 101           mov     ebx, eax                            ; eax is unchanged from loop
 102           jmp     .end
 103
 104      ;----------------------------------------------;
 105      ; no next block exists, make a new header at   ;
 106      ; the end of the requested size with the       ;
 107      ; reminder of the free space, and update the   ;
 108      ; prev header's next pointer..                 ;
 109      ;----------------------------------------------;
 110      .prev_but_no_next:
 111           mov     ecx, eax                            ; move address to ecx and
 112           add     ecx, ebx                            ; add size. ecx=end requested
 113           mov     edx, [prev_pointer]                 ; set prev for new header
 114           mov     [ecx], edx                          ; set new header's prev to 0
 115           mov     edx, [size]
 116           sub     edx, ebx                            ; remaining space in edx
 117           mov     [ecx+4], edx                        ; save it to new header
 118           mov     dword [ecx+8], 0                    ; no next pointer..
 119
 120           mov     [prev_pointer+8], ecx
 121           mov     ebx, eax                            ; eax is unchanged from loop
 122           jmp     .end
 123
 124
 125      ;----------------------------------------------;
 126      ; both next and previous blocks exists, make a ;
 127      ; new header at the end of the requested size  ;
 128      ; with the reminder of the free space, move    ;
 129      ; data from next block to the new one but add  ;
 130      ; size so it gets right, then update all prev/ ;
 131      ; next pointers for total 3 blocks.. puh..     ;
 132      ;----------------------------------------------;
 133      .next_exists:
 134           cmp     [prev_pointer], 0
 135           je      .next_but_no_prev
 136
 137           mov     ecx, eax                            ; move address to ecx and
 138           add     ecx, ebx                            ; add size. ecx=end requested
 139           mov     edx, [prev_pointer]                 ; set prev for new header
 140           mov     [ecx], edx                          ; set new header's prev
 141           mov     edx, [size]
 142           sub     edx, ebx
 143           mov     ebx, [next_pointer+4]
 144           add     edx, ebx                            ; remaining space in edx
 145           mov     [ecx+4], edx                        ; save it to new header
 146           mov     edx, [next_pointer]                 ; address to next block
 147           cmp     dword [edx], 0
 148           je      .no_next_next
 149           mov     dword [edx], ecx                    ; update next-next's prev..
 150           mov     dword [ecx+8], edx                  ; address to next pointer.
 151
 152           mov     [prev_pointer+8], ecx
 153           mov     ebx, eax                            ; eax is unchanged from loop
 154           jmp     .end
 155      .no_next_next:
 156           mov     dword [edx], 0
 157           mov     dword [ecx+8], 0
 158           mov     [prev_pointer+8], ecx
 159           mov     ebx, eax                            ; eax is unchanged from loop
 160           jmp     .end
 161
 162
 163      ;----------------------------------------------;
 164      ; we allocated the first free block, do the    ;
 165      ; same as above, except ignore the prev block  ;
 166      ; part, and move the "first free".             ;
 167      ;----------------------------------------------;
 168      .next_but_no_prev:
 169           mov     ecx, eax                            ; move address to ecx and
 170           add     ecx, ebx                            ; add size. ecx=end requested
 171           mov     dword [ecx], 0                      ; set new header's prev to 0
 172           mov     edx, [size]
 173           sub     edx, ebx
 174           mov     ebx, [next_pointer+4]
 175           add     edx, ebx                            ; remaining space in edx
 176           mov     [ecx+4], edx                        ; save it to new header
 177           mov     edx, [next_pointer]                 ; address to next block
 178           cmp     dword [edx], 0
 179           je      .no_next_next2
 180           mov     dword [edx], ecx                    ; update next-next's prev..
 181           mov     dword [ecx+8], edx                  ; address to next pointer.
 182
 183           mov     [first_free], ecx                   ; zero and update first free.
 184           mov     ebx, eax                            ; eax is unchanged from loop
 185           jmp     .end
 186      .no_next_next2:
 187           mov     dword [edx], 0
 188           mov     ecx, [ecx+8]
 189           mov     dword [ecx], 0
 190           mov     [prev_pointer+8], ecx
 191           mov     ebx, eax                            ; eax is unchanged from loop
 192           jmp     .end
 193
 194
 195      ;-----------------------------------------;
 196      ;   requested == size                     ;
 197      ;   I prefered coding this one.. ;)       ;
 198      ;-----------------------------------------;
 199      .equal:
 200           cmp     [next_pointer], 0
 201           jne     .next_exists2
 202           cmp     [prev_pointer], 0
 203           jne     .prev_but_no_next2
 204           mov     [first_free], 0
 205           mov     ebx, eax                            ; eax is unchanged from loop
 206           jmp     .end
 207
 208      .prev_but_no_next2:
 209           mov     dword [prev_pointer+8], 0
 210           mov     ebx, eax                            ; eax is unchanged from loop
 211           jmp     .end
 212
 213      .next_exists2:
 214           cmp     [prev_pointer], 0
 215           je      .next_but_no_prev2
 216           mov     ecx, [prev_pointer]                 ; update prev and next's
 217           mov     edx, [next_pointer]                 ; headers to bypass this
 218           mov     [ecx+8], edx                        ; chunk.
 219           mov     [edx], ecx
 220           mov     ebx, eax                            ; eax is unchanged from loop
 221           jmp     .end
 222
 223      .next_but_no_prev2:
 224           mov     ecx, [eax+8]                        ; get address of next header
 225           mov     dword [ecx], 0                      ; set prev in next header to
 226           mov     [first_free], ecx                   ; zero and update first free.
 227           mov     ebx, eax                            ; eax is unchanged from loop
 228
 229      .end:
 230           pop     edx
 231           pop     ecx
 232           ret
 233
 234
 235
 236
 237 ;------------------------------------------------------;
 238 ;    free memory                                       ;
 239 ;                  in:  ebx = pointer to mem           ;
 240 ;                       ecx = size in bytes            ;
 241 ;------------------------------------------------------;
 242 free_mem:
 243           push    eax
 244           push    ebx
 245           push    ecx
 246           push    edx
 247
 248           cmp     ebx, [first_free]
 249           jb      .new_first_free
 250           cmp     [first_free], 0
 251           je      .new_first_free
 252
 253      ;-----------------------------------------------------------;
 254      ; the block we want to free is somewhere in between         ;
 255      ; two other free blocks or after the last free block.       ;
 256      ; search for the "ebx"-address, so we know where the new    ;
 257      ; prev/next pointers are, and then can check if we should   ;
 258      ; merge blocks..                                            ;
 259      ;-----------------------------------------------------------;
 260           mov     eax, [first_free]                   ; "current" free block
 261           mov     edx, [eax+8]                        ; next free block
 262
 263      .find_pos_loop:
 264           cmp     edx, 0                              ; check if the "next"
 265           je      .found_end_of_ram                   ; free exists..
 266
 267           cmp     ebx, edx                            ; is ebx "below" edx?
 268           jb      .found_between                      ; found ebx in between
 269
 270           mov     eax, edx                            ; update pointers for
 271           mov     edx, [eax+8]                        ; another loop.
 272           jmp     .find_pos_loop
 273
 274      ;------------------------------------------;
 275      ;  the block is between two other blocks   ;
 276      ;------------------------------------------;
 277      .found_between:
 278           mov     [ebx], eax                          ; create header
 279           mov     [ebx+4], ecx
 280           mov     [ebx+8], edx
 281
 282           mov     [eax+8], ebx                        ; update prev header
 283           mov     [edx], ebx                          ; update next header
 284
 285           ; now check if we can merge blocks....
 286           add     ecx, ebx
 287           cmp     edx, ecx
 288           jne     .merge_only_first
 289           push    eax
 290           add     eax, [eax+4]
 291           cmp     ebx, eax
 292           pop     eax
 293           jne     .merge_only_last
 294
 295           ; we can merge with both prev & next
 296           mov     ecx, [ebx+4]                        ; get size from "current"
 297           add     [eax+4], ecx                        ; and add it to "prev".
 298           mov     ecx, [edx+4]                        ; get size from "next"
 299           add     [eax+4], ecx                        ; and add it to "prev".
 300           mov     ecx, [edx+8]                        ; get the new next
 301           mov     [eax+8], ecx                        ; pointer, and store it.
 302           cmp     ecx, 0
 303           je      .end
 304           mov     [ecx], eax
 305           jmp     .end
 306
 307      .merge_only_first:
 308           cmp     ebx, eax
 309           jne     .end
 310           mov     ecx, [ebx+4]                        ; get size from "current"
 311           add     [eax+4], ecx                        ; and add it to "prev".
 312           mov     [edx], eax                          ; update prev and next
 313           mov     [eax+8], edx                        ; pointers for the two..
 314           jmp     .end
 315
 316      .merge_only_last:
 317           cmp     edx, ecx
 318           jne     .end
 319           mov     ecx, [edx+4]
 320           add     [ebx+4], ecx
 321           mov     ecx, [edx+8]
 322           mov     [ebx+8], ecx
 323           cmp     ecx, 0
 324           je      .end
 325           mov     [ecx], ebx
 326           jmp     .end
 327
 328      ;----------------------------------------------;
 329      ;  the block is after all existing free ones   ;
 330      ;----------------------------------------------;
 331      .found_end_of_ram:
 332           mov     [ebx], eax                          ; create header
 333           mov     [ebx+4], ecx
 334           mov     [ebx+8], edx
 335
 336           mov     [eax+8], ebx                        ; update prev header
 337
 338           ; now check if we can merge the blocks....
 339           mov     ecx, eax
 340           add     ecx, [eax+4]
 341           cmp     ebx, ecx
 342           jne     .end
 343           mov     ecx, [ebx+4]
 344           add     [eax+4], ecx
 345           mov     ecx, [ebx+8]
 346           mov     [eax+8], ecx
 347           jmp     .end
 348
 349      ;--------------------------------------------;
 350      ;  the block is before any other free ones   ;
 351      ;--------------------------------------------;
 352      .new_first_free:
 353           mov     dword [ebx], 0
 354           mov     [ebx+4], ecx                        ; create the
 355           mov     edx, [first_free]                   ; new header
 356           mov     [ebx+8], edx
 357
 358           mov     edx, ebx                            ; check if the
 359           add     edx, [ebx+4]                        ; first_free matches
 360           cmp     edx, [first_free]                   ; current pos + size?
 361           je      .merge_first_free                   ; if so, merge the two
 362
 363           cmp     [first_free], 0                     ; else check if
 364           je      .cont1                              ; first_free exists
 365           mov     edx, [ebx+8]                        ; if it does, update
 366           mov     [edx], ebx                          ; it's prev pointer.
 367      .cont1:
 368           mov     [first_free], ebx                   ; else/and set new
 369           jmp     .end                                ; first free and quit
 370
 371      .merge_first_free:                               ; merge the two first
 372           mov     edx, [ebx+8]                        ; add the size of the
 373           mov     ecx, [edx+4]                        ; second block to the
 374           add     [ebx+4], ecx                        ; new one.
 375           mov     ecx, [edx+8]                        ; get the next pointer
 376           mov     [ebx+8], ecx                        ; from the old block,
 377           cmp     ecx, 0
 378           je      .cont2
 379           mov     [ecx], ebx                          ; update this + next..
 380      .cont2:
 381           mov     [first_free], ebx                   ; update first_free
 382
 383      .end:
 384           pop     edx
 385           pop     ecx
 386           pop     ebx
 387           pop     eax
 388           ret