Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. if ~ used memalloc_inc
  2. memalloc_inc_fix:
  3. memalloc_inc fix memalloc_inc_fix
  4. ;kglobals.inc required.
  5. ;multithread:  ;uncomment this for thread-safe version
  6. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  7. ;; Memory allocator for MenuetOS                         ;;
  8. ;; Halyavin Andrey halyavin@land.ru, 2006                ;;
  9. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  10.  
  11. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  12. ;; allocated mem block structure                         ;;
  13. ;; +0:   bit 0 - used flag                               ;;
  14. ;;       bits 31..1 - block size                         ;;
  15. ;; +4: address of prev block                             ;;
  16. ;; +8 .. +(blocksize) - allocated memory                 ;;
  17. ;; +(blocksize) - next block                             ;;
  18. ;;                                                       ;;
  19. ;; free mem block structure                              ;;
  20. ;; +0:   bit 0 - used flag                               ;;
  21. ;;       bits 31..1 - block size                         ;;
  22. ;; +4:  address of prev block                            ;;
  23. ;; +8:  prev free block                                  ;;
  24. ;; +12: next free block                                  ;;
  25. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  26. memblock.size=0
  27. memblock.prevblock=4
  28. memblock.prevfreeblock=8
  29. memblock.nextfreeblock=12
  30. uglobal
  31.     heapsmallblocks rd 1
  32.     heapstart       rd 1
  33.     heapend         rd 1
  34.     heapfreelist    rd 1
  35.     heapmutex       rd 1
  36.     heaplastblock   rd 1
  37. endg
  38.  
  39. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  40. ;; mf_init                                               ;;
  41. ;; Initialize memory map for dynamic use                 ;;
  42. ;; input: eax: starting address or 0                     ;;
  43. ;; output: none                                          ;;
  44. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  45. mf_init:
  46.   push ebx
  47.   push ecx
  48.   test eax,eax
  49.   jnz  .noautodet
  50.   sub  esp,1024
  51.   mov  ebx,esp
  52.   mov  ecx,-1
  53.   mov  eax,9
  54.   int  0x40
  55.   mov  eax,[esp+26]
  56.   add  esp,1024
  57. .noautodet:
  58.   add  eax,15
  59.   and  eax,not 15
  60.   mov  [heapsmallblocks],eax
  61.   add  eax,2048
  62.   mov  [heapstart],eax
  63.   mov  [heapfreelist],eax
  64.   mov  [heaplastblock],eax
  65.  
  66.   mov  ecx,eax
  67. if defined heapstartsize
  68.   add  ecx,heapstartsize
  69. else
  70.   add  ecx,4096
  71. end if
  72.   add  ecx,4095
  73.   and  ecx,not 4095
  74.   push eax
  75.   mov  eax,64
  76.   mov  ebx,1
  77.   int  0x40
  78.   pop  eax
  79.   mov  [eax+memblock.prevblock],dword 0  
  80.   mov  [heapend],ecx
  81.   mov  [eax+memblock.size],ecx
  82.   sub  [eax+memblock.size],eax
  83.   xor  ebx,ebx
  84.   mov  dword [eax+memblock.prevfreeblock],heapfreelist-memblock.nextfreeblock
  85.   mov  [eax+memblock.nextfreeblock],ebx
  86.   mov  [heapmutex],ebx
  87.   push edi
  88.   mov  edi,[heapsmallblocks]
  89.   mov  ecx,512
  90.   xor  eax,eax
  91.   rep  stosd
  92.   pop  edi
  93.   pop  ecx
  94.   pop  ebx
  95.   ret
  96.  
  97. if defined multithread
  98. heaplock:
  99.   push eax
  100.   push ebx
  101.   mov  eax,68
  102.   mov  ebx,1
  103. .loop:
  104.   xchg eax,[heapmutex]
  105.   test eax,eax
  106.   jz   .endloop
  107.   int  0x40     ;change task
  108.   jmp  .loop
  109. .endloop:
  110.   pop  ebx
  111.   pop  eax
  112.   ret
  113.  
  114. heapunlock:
  115.   mov  [heapmutex],dword 0
  116.   ret
  117. end if
  118.  
  119. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  120. ;; heap_split_block                                      ;;
  121. ;; Split free block to allocated block and free one.     ;;
  122. ;; input:                                                ;;
  123. ;;   eax - size of allocated block                       ;;
  124. ;;   ebx - block                                         ;;
  125. ;; output:                                               ;;
  126. ;;   eax - real size of allocated block                  ;;
  127. ;;   ebx - pointer to new block                          ;;
  128. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  129. heap_split_block:
  130.   push ecx
  131.   mov  ecx,[ebx+memblock.size]
  132.   sub  ecx,16
  133.   cmp  ecx,eax
  134.   jge  .norm
  135.   inc  dword [ebx+memblock.size]
  136.   mov  eax,ecx
  137.   xor  ebx,ebx
  138.   pop  ecx
  139.   ret
  140. .norm:
  141.   add  ecx,16
  142.   mov  [ebx+memblock.size],eax
  143.   inc  dword [ebx+memblock.size]
  144.   mov  [ebx+eax+memblock.prevblock],ebx
  145.   add  ebx,eax
  146.   sub  ecx,eax
  147.   mov  [ebx+memblock.size],ecx
  148.   mov  ecx,eax
  149.   mov  eax,ebx
  150.   call heap_fix_right
  151.   mov  eax,ecx
  152.   pop  ecx
  153.   ret
  154.  
  155. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  156. ;; heap_add_free_block                                   ;;
  157. ;; Add free block to one of free block lists.            ;;
  158. ;; input:                                                ;;
  159. ;;   eax - address of free block                         ;;
  160. ;; output:                                               ;;
  161. ;;   none                                                ;;
  162. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  163. heap_add_free_block:
  164.   cmp  dword [eax+memblock.size],4096
  165.   push ebx
  166.   jge  .bigblock
  167.   mov  ebx,[eax+memblock.size]
  168.   shr  ebx,1
  169.   add  ebx,[heapsmallblocks]
  170.   push dword [ebx]
  171.   pop  dword [eax+memblock.nextfreeblock]
  172.   mov  [ebx],eax
  173.   mov  dword [eax+memblock.prevfreeblock],ebx
  174.   sub  dword [eax+memblock.prevfreeblock],memblock.nextfreeblock
  175.   mov  ebx,[eax+memblock.nextfreeblock]
  176.   test ebx,ebx
  177.   jz   .no_next_block
  178.   mov  [ebx+memblock.prevfreeblock],eax
  179. .no_next_block:
  180.   pop  ebx
  181.   ret
  182. .bigblock:
  183.   mov  ebx,[heapfreelist]
  184.   mov  [eax+memblock.nextfreeblock],ebx
  185.   mov  [heapfreelist],eax
  186.   mov  dword [eax+memblock.prevfreeblock],heapfreelist-memblock.nextfreeblock
  187. ;  mov  ebx,[eax+memblock.nextfreeblock]
  188.   test ebx,ebx
  189.   jz   .no_next_big_block
  190.   mov  [ebx+memblock.prevfreeblock],eax
  191. .no_next_big_block:
  192.   pop  ebx
  193.   ret
  194.  
  195. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  196. ;; heap_remove_block                                     ;;
  197. ;; Remove free block from the list of free blocks.       ;;
  198. ;; input:                                                ;;
  199. ;;   eax - free block                                    ;;
  200. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  201. heap_remove_block:
  202.   push  ebx
  203.   push  ecx
  204.   mov   ecx,[eax+memblock.prevfreeblock]
  205.   mov   ebx,[eax+memblock.nextfreeblock]
  206.   mov   [ecx+memblock.nextfreeblock],ebx
  207.   test  ebx,ebx
  208.   jz    .no_next_block
  209.   mov   [ebx+memblock.prevfreeblock],ecx
  210. .no_next_block:
  211.   pop   ecx
  212.   pop   ebx
  213.   ret
  214.  
  215. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  216. ;; mf_alloc
  217. ;; allocates a block of memory in heap
  218. ;; intput: eax: size of block
  219. ;; output: eax: address of allocated memory block or 0 if there's no mem.
  220. ;; allocator will not create new nodes that contain less that 8b of space,
  221. ;; and minimal allocation is actually 16 bytes - 8 for node and 8 for user.
  222. ;; allocator will never create non-aligned memory blocks.
  223. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  224. mf_alloc:
  225.   test eax,eax
  226.   jg   .not_null  ; test that we are not allocating null size block
  227.   xor  eax,eax
  228.   ret
  229. .not_null:
  230. if defined multithread
  231.   call heaplock
  232. end if
  233.   push edi
  234. ;  push edx
  235.   push ecx
  236.   push ebx
  237.   add  eax,7
  238.   and  eax,not 7   ; make sure that block size is aligned
  239.  
  240.   lea  edi,[eax+8] ; desired block size
  241.   cmp  edi,4096
  242.   jge  .general_cycle
  243.  
  244.   mov  ebx,[heapsmallblocks]
  245.   xor  ecx,ecx
  246.   shr  edi,1
  247.  
  248. .smallloop:
  249.   cmp  [ebx+edi],ecx
  250.   jnz  .smallblockfound
  251.   add  edi,4
  252.   cmp  edi,2048
  253.   jl   .smallloop
  254.   lea  edi,[eax+8]
  255.   jmp  .general_cycle
  256.  
  257. .smallblockfound:
  258.   lea  ecx,[eax+8]
  259.   mov  eax,[ebx+edi]
  260.   call heap_remove_block
  261.   mov  ebx,eax
  262.   xchg eax,ecx
  263.   call heap_split_block
  264.   test ebx,ebx
  265.   jz   .perfect_small_block
  266.   mov  eax,ebx
  267.   call heap_add_free_block
  268. .perfect_small_block:
  269.   lea  eax,[ecx+8]
  270.   jmp  .ret
  271.  
  272. .general_cycle:
  273. ;edi - size needed
  274.   mov  eax,[heapfreelist]
  275.  
  276. .loop:
  277.   test eax,eax
  278.   jz   .new_mem
  279.   cmp  [eax+memblock.size],edi
  280.   jge  .blockfound
  281.   mov  eax,[eax+memblock.nextfreeblock]
  282.   jmp  .loop
  283.  
  284. .blockfound:
  285.   call heap_remove_block
  286.   mov  ebx,eax
  287.   mov  ecx,eax
  288.   mov  eax,edi
  289.   call heap_split_block
  290.   test ebx,ebx
  291.   jz   .perfect_block
  292.   mov  eax,ebx
  293.   call heap_add_free_block
  294. .perfect_block:
  295.   lea  eax,[ecx+8]
  296. .ret:
  297. if defined multithread
  298.   call heapunlock
  299. end if
  300.   pop  ebx
  301.   pop  ecx
  302. ;  pop  edx
  303.   pop  edi
  304.   ret
  305.  
  306. .new_mem:
  307.   mov  eax,edi
  308.   add  eax,4095
  309.   and  eax,not 4095
  310.   mov  ecx,[heapend]
  311.   add  [heapend],eax
  312.   push eax
  313.   mov  eax,64
  314.   push ebx
  315.   push ecx
  316.   mov  ecx,[heapend]
  317.   mov  ebx,1
  318.   int  0x40
  319.   pop  ecx
  320.   pop  ebx
  321.   pop  eax
  322.   mov  [ecx+memblock.size],eax
  323.   mov  eax,[heaplastblock]
  324.   mov  [ecx+memblock.prevblock],eax
  325.   mov  [heaplastblock],ecx
  326.   mov  eax,ecx
  327.   call heap_add_free_block
  328.   jmp  .general_cycle
  329.  
  330. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  331. ;; heap_fix_right                                        ;;
  332. ;; input:                                                ;;
  333. ;;   eax - pointer to free block                         ;;
  334. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  335. heap_fix_right:
  336.   push ebx
  337.   mov  ebx,eax
  338.   add  ebx,[eax+memblock.size]
  339.   cmp  ebx,[heapend]
  340.   jz   .endblock
  341.   mov  [ebx+memblock.prevblock],eax
  342.   pop  ebx
  343.   ret
  344. .endblock:
  345.   mov  [heaplastblock],eax
  346.   pop  ebx
  347.   ret
  348.  
  349. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  350. ;; heap_merge_left                                       ;;
  351. ;; input:                                                ;;
  352. ;;   eax - pointer to free block                         ;;
  353. ;; output:                                               ;;
  354. ;;   eax - pointer to merged block                       ;;
  355. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  356. heap_merge_left:
  357.   push ebx
  358.   mov  ebx,[eax+memblock.prevblock]
  359.   test ebx,ebx
  360.   jz   .ret
  361.   test byte [ebx+memblock.size],1
  362.   jnz  .ret
  363.   xchg eax,ebx
  364.   call heap_remove_block
  365.   mov  ebx,[ebx+memblock.size]
  366.   add  [eax+memblock.size],ebx
  367.   call heap_fix_right
  368. .ret:
  369.   pop  ebx
  370.   ret
  371.  
  372. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  373. ;; heap_merge_right                                      ;;
  374. ;; input:                                                ;;
  375. ;;   eax - pointer to free block                         ;;
  376. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  377. heap_merge_right:
  378.   push ebx
  379.   mov  ebx,eax
  380.   add  ebx,[eax+memblock.size]
  381.   cmp  ebx,[heapend]
  382.   jz   .ret
  383.   test byte [ebx+memblock.size],1
  384.   jnz  .ret
  385.   xchg eax,ebx
  386.   call heap_remove_block
  387.   xchg eax,ebx
  388.   mov  ebx,[ebx+memblock.size]
  389.   add  [eax+memblock.size],ebx
  390.   call heap_fix_right
  391. .ret:
  392.   pop  ebx
  393.   ret
  394.  
  395. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  396. ;; mf_free                                               ;;
  397. ;; input:                                                ;;
  398. ;;   eax - pointer                                       ;;
  399. ;; output:                                               ;;
  400. ;;   eax=1 - ok                                          ;;
  401. ;;   eax=0 - failed                                      ;;
  402. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  403. mf_free:
  404.   test eax,eax
  405.   jnz  .no_null
  406.   inc  eax
  407.   ret
  408. .no_null:
  409. if defined multithread
  410.   call heaplock
  411. end if
  412.   sub  eax,8
  413.   dec  dword [eax+memblock.size]
  414.   call heap_merge_left
  415.   call heap_merge_right
  416.   call heap_add_free_block
  417. .ret:
  418. if defined multithread
  419.   call heapunlock
  420. end if
  421.   ret
  422.  
  423. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  424. ;; heap_try_reloc
  425. ;; input:
  426. ;;   eax - address
  427. ;;   ebx - new size
  428. ;; output:
  429. ;;   ebx=1 - ok
  430. ;;   ebx=0 - failed
  431. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  432. heap_try_reloc:
  433.   push eax
  434.   sub  eax,8
  435.   add  ebx,15
  436.   dec  dword [eax+memblock.size]
  437.   and  ebx,not 7
  438.   cmp  [eax+memblock.size],ebx
  439.   jge  .truncate
  440.   push ebx
  441.   mov  ebx,eax
  442.   add  ebx,[eax+memblock.size]
  443.   cmp  ebx,[heapend]
  444.   jz   .fail  ;todo: we can allocate new mem here
  445.   test [ebx+memblock.size],byte 1
  446.   jnz  .fail
  447.   xchg eax,ebx
  448.   call heap_remove_block
  449.   mov  eax,[eax+memblock.size]
  450.   add  [ebx+memblock.size],eax
  451.   mov  eax,ebx
  452.   call heap_fix_right
  453.   pop  ebx
  454. .truncate:
  455.   xchg eax,ebx
  456.   call heap_split_block
  457.   test ebx,ebx
  458.   jz   .no_last_block
  459.   mov  eax,ebx
  460.   call heap_add_free_block
  461.   call heap_merge_right
  462. .no_last_block:
  463.   xor  ebx,ebx
  464.   pop  eax
  465.   inc  ebx
  466.   ret
  467. .fail:
  468.   pop  ebx
  469.   xor  ebx,ebx
  470.   pop  eax
  471.   inc  dword [eax-8+memblock.size]
  472.   ret
  473.  
  474. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  475. ;; mf_realloc
  476. ;; input:
  477. ;;   eax - pointer
  478. ;;   ebx - new size
  479. ;; output:
  480. ;;   eax - new pointer
  481. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  482. mf_realloc:
  483.   push ebx
  484. if defined multithread
  485.   call heaplock
  486. end if
  487.   call heap_try_reloc
  488.   test ebx,ebx
  489.   jnz  .ret
  490. ;allocate new memory
  491.   push eax
  492.   mov  eax,[esp+4]
  493.   call mf_alloc
  494.   test eax,eax
  495.   jz   .fail
  496.   push esi
  497.   push edi
  498.   push ecx
  499.   mov  edi,eax
  500.   mov  esi,[esp+12]
  501.   mov  ecx,[esi-8+memblock.size]
  502.   shr  ecx,2
  503.   rep  movsd
  504.   pop  ecx
  505.   pop  edi
  506.   pop  esi
  507.   xchg eax,[esp]
  508.   call mf_free
  509. .fail:
  510.   pop  eax
  511. .ret:
  512. if defined multithread
  513.   call heapunlock
  514. end if
  515.   pop  ebx
  516.   ret
  517. end if
  518.