home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / salloc / alloc3.s < prev    next >
Encoding:
Text File  |  1975-05-13  |  5.9 KB  |  433 lines
  1. .globl    flag
  2. .globl    b1, w1, u1, b1s, b1e
  3. /    here to allocate a new block
  4. /
  5. /
  6. /    mov    ...,r0
  7. /    jsr    pc,allocate
  8. /    mov    r1,...
  9. /
  10. /    requested size in bytes in r0
  11. /    pointer to header of allocated block returned in r1
  12. /    r0 is preserved
  13. /
  14. /    convert to words, adjust for header, round up
  15. /    to a power of two
  16. /
  17. /    each block has a four-word header
  18. /        W - write ptr (also used as link ptr in frlist)
  19. /        R - read ptr
  20. /        A - pointer to head of data
  21. /        L - ptr to (end+1) of data
  22. hsz=1024.
  23. numb=4.
  24. numb2=2*numb
  25. w=0
  26. r=2
  27. a=4
  28. l=6
  29. /
  30. allocate:
  31.     mov    r0,-(sp)
  32.     mov    r2,-(sp)
  33.     mov    r3,-(sp)
  34.     tst    stats
  35.     bne    1f
  36.     jsr    pc,initl
  37. 1:
  38.     inc    stats
  39.     dec    r0
  40.     bmi    1f
  41.     jsr    pc,log2
  42.     inc    r0
  43. 1:    asl    r0
  44.     mov    r0,-(sp)
  45. /
  46. /    look on free list for block of required size
  47. /
  48. zzz:
  49.     mov    (sp),r0
  50.     tst    frlist(r0)
  51.     beq    xxx
  52. /
  53. /    found it, allocate and return
  54. /
  55.     mov    frlist(r0),r1
  56.     add    $hblk,r1
  57.     mov    (r1),frlist(r0)
  58.     mov    a(r1),r0
  59.     mov    r0,w(r1)
  60.     mov    r0,r(r1)
  61.     tst    (sp)+
  62.     mov    (sp)+,r3
  63.     mov    (sp)+,r2
  64.     mov    (sp)+,r0
  65. /    jsr    pc,whead
  66.     rts    pc
  67. /
  68. /    no block of required size
  69. /    look for larger block
  70. /
  71. xxx:
  72.     tst    (r0)+
  73.     cmp    r0,$frend-frlist
  74.     bhis    www
  75.     tst    frlist(r0)
  76.     bne    yyy
  77.     br    xxx
  78. /
  79. /    there are no larger blocks;  must garbage collect
  80. /
  81. www:    jsr    pc,collect
  82.     tst    r0
  83.     bne    zzz
  84. /
  85. /    out of space
  86. /
  87.     mov    $1,r0
  88.     sys    write; 1f; 2f-1f
  89.     4
  90. 1:    <Out of space.\n>
  91. 2:    .even
  92. /
  93. /    split larger block into two smaller pieces and
  94. /    link together as smaller blocks in the free list.
  95. /
  96. yyy:
  97.     mov    hblk,r3    /get free header block
  98.     beq    www
  99.     mov    frlist(r0),r1
  100.     add    $hblk,r1
  101.     mov    w(r1),frlist(r0)
  102.     mov    r3,w(r1)
  103.     add    $hblk,r3
  104.     mov    exp2-2(r0),r2
  105.     add    a(r1),r2
  106.     mov    w(r3),hblk
  107.     mov    l(r1),l(r3)
  108.     mov    r2,l(r1)        /L
  109.     mov    r2,a(r3)
  110.     clr    w(r3)            /W'
  111.     mov    r1,r2
  112.     sub    $hblk,r2
  113.     mov    r2,frlist-2(r0)
  114.     br    zzz
  115. /
  116. /
  117. /    here to release a block
  118. /
  119. /    mov    ...,r1
  120. /    jsr    pc,release
  121. /
  122. /    pointer to block in r1
  123. /
  124. release:
  125. /
  126. /    discover that this is a plausible pointer
  127. /
  128.     mov    r0,-(sp)
  129.     jsr    pc,preposterous
  130. /
  131. /    find free list index and link block to that entry
  132. /
  133.     inc    stats+2
  134.     mov    frlist(r0),w(r1)
  135.     clr    r(r1)
  136.     sub    $hblk,r1
  137.     mov    r1,frlist(r0)
  138.     clr    r1        /self-defense
  139. /    jsr    pc,whead
  140.     mov    (sp)+,r0
  141.     rts    pc
  142. /
  143. /
  144. /    jsr    pc,collect
  145. /
  146. /    coalesce free storage by rejoining paired blocks
  147. /    on the free list.
  148. /    zero is returned in r0 if no paired blocks were found.
  149. /
  150. collect:
  151.     mov    r1,-(sp)
  152.     mov    r2,-(sp)
  153.     mov    r3,-(sp)
  154.     mov    r4,-(sp)
  155.     clr    useful
  156.     inc    stats+4.
  157.     clr    r0        /start with smallest blocks
  158.                 /r0 contains frlist index
  159. loop1:    mov    $frlist,r1
  160.     add    r0,r1
  161. /
  162. /    try next list member at this level
  163. /
  164. loop2:    mov    (r1),r3
  165.     beq    advance        /list is empty
  166.     add    $hblk,r3
  167.     tst    (r3)        /W
  168.     beq    advance        /only one list element
  169. /
  170. /    calculate address of buddy
  171. /
  172.     mov    a(r3),r4
  173.     sub    headsz,r4
  174.     bit    exp2(r0),r4
  175.     beq    2f
  176.     bic    exp2(r0),r4
  177.     br    1f
  178. 2:    bis    exp2(r0),r4
  179. 1:    add    headsz,r4
  180. /
  181. /    and search for him
  182. /
  183. loop3:
  184.     cmp    a(r3),r4
  185.     beq    coal
  186.     mov    r3,r2
  187.     mov    w(r3),r3
  188.     tst    r3
  189.     beq    nocoal
  190.     add    $hblk,r3
  191.     br    loop3
  192. /
  193. /    have found a pair; remove both blocks from list,
  194. /    coalesce them, and put them on next higher list
  195. /
  196. coal:    inc    useful
  197.     mov    w(r3),w(r2)    /remove him from list
  198.     mov    (r1),r2
  199.     add    $hblk,r2
  200.     mov    r3,r4
  201.     mov    w(r2),w(r1)    /remove other one
  202.     cmp    a(r2),a(r4)
  203.     bgt    1f
  204.     mov    r2,-(sp)
  205.     mov    r4,r2
  206.     mov    (sp)+,r4
  207. 1:    mov    hblk,(r2)
  208.     clr    r(r2)
  209.     mov    headsz,a(r2)
  210.     mov    headsz,l(r2)
  211.     sub    $hblk,r2
  212.     mov    r2,hblk
  213.     add    exp2(r0),l(r4)    /L
  214.     clr    r(r4)
  215.     mov    frlist+2(r0),w(r4)
  216.     sub    $hblk,r4
  217.     mov    r4,frlist+2(r0)
  218.     br    loop2
  219. /
  220. /    no buddy found, try next block on this list
  221. /
  222. nocoal:
  223.     mov    (r1),r1
  224.     add    $hblk,r1
  225.     br    loop2
  226. /
  227. /    advance to next free list
  228. /
  229. advance:
  230.     tst    (r0)+
  231.     cmp    r0,$frend-frlist
  232.     blo    loop1
  233.     mov    useful,r0
  234. /
  235. /    restore registers and return
  236. /
  237.     mov    (sp)+,r4
  238.     mov    (sp)+,r3
  239.     mov    (sp)+,r2
  240.     mov    (sp)+,r1
  241.     rts    pc
  242. /
  243. /    routine to find integer part of log2(x)
  244. /
  245. /    jsr    pc,log2
  246. /
  247. /    r0 = log2(r0)
  248. /
  249. log2:
  250.     mov    $15.,-(sp)
  251.     tst    r0
  252.     beq    2f
  253. 1:
  254.     asl    r0
  255.     bcs    2f
  256.     dec    (sp)
  257.     br    1b
  258. 2:
  259.     mov    (sp)+,r0
  260.     rts    pc
  261. /
  262.     0
  263. exp2:
  264.     1;2;4;10;20;40;100;200;400;1000;2000;4000;
  265.     10000;20000;40000;100000
  266. /
  267. /    routine to discover whether r1 points to
  268. /    a plausible header - to avoid ruination.
  269. /
  270. /    r1 is preserved and r0 gets a suitable index for frlist
  271. /
  272. /    jsr    pc,preposterous
  273. /
  274. plausible:
  275.     cmp    r1,$strbuf
  276.     blo    botch
  277.     cmp    r1,$strend
  278.     bhis    botch
  279.     rts    pc
  280. /
  281. /
  282. botch:
  283.     mov    r0,-(sp)
  284.     mov    $1,r0
  285.     sys    write; 1f; 2f-1f
  286.     4
  287. 1:    <Error in allocator.\n>
  288. 2:    .even
  289. /
  290. /
  291. preposterous:
  292.     cmp    r1,$strbuf
  293.     blo    botch
  294.     cmp    r1,$strend
  295.     bhis    botch
  296.     cmp    a(r1),headsz        /A
  297.     blo    botch
  298.     cmp    l(r1),datadr        /L
  299.     bhi    botch
  300.     mov    l(r1),r0        /L
  301.     sub    a(r1),r0        /A
  302.     mov    r0,-(sp)
  303.     jsr    pc,log2
  304.     asl    r0
  305.     cmp    exp2(r0),(sp)
  306.     bne    botch
  307.     mov    r0,(sp)
  308.     mov    frlist(r0),r0
  309. 1:    beq    1f
  310.     add    $hblk,r0
  311.     cmp    r0,r1
  312.     beq    botch
  313.     mov    (r0),r0
  314.     br    1b
  315. 1:    mov    (sp)+,r0
  316.     rts pc
  317. /
  318. /
  319. whead:
  320.     mov    r0,-(sp)
  321.     mov    afout,r0
  322.     sys    seek;0;0    /write pointer to 0
  323.     sys    write;hblk;hsz
  324.     mov    (sp)+,r0
  325.     rts    pc
  326. /
  327. datasz:    16384.
  328. headsz: hsz
  329. nbuf: numb
  330. nbuf2: numb2
  331.  
  332. b1s:    .=.+numb2
  333. b1e:    .=.+ numb2
  334. w1:    .=.+ numb2
  335. u1:    .=.+ numb2
  336. b1 = .
  337. /
  338. initl:
  339.     mov    r0,-(sp)
  340.     mov    r2,-(sp)
  341.     sys    open;asmem; 1    /open for write
  342.     bec    2f
  343.     sys    creat;asmem; 606
  344.     bes    err2
  345. 2:
  346.     mov    r0,afout
  347. 1:
  348.     sys    open; asmem; 0    /open for read
  349.     bes    err2
  350.     mov    r0,afi
  351. 1:
  352.     br    gargs
  353. /
  354. err2:
  355.     mov    $1,r0
  356.     sys    write; 1f; 2f-1f
  357.     4
  358. 1:    <cannot open output file\n>
  359. 2:
  360. asmem:
  361.     <alloc.d\0>
  362.     .even
  363. /
  364. gargs:
  365.     mov    $headers,r2
  366.     mov    r2,r0
  367.     sub    $hblk,r0
  368.     mov    r0,hblk
  369. 1:
  370.     add    $8,r0
  371.     mov    r0,(r2)
  372.     add    $8,r2
  373.     cmp    r2,$strend-8.
  374.     blo    1b
  375.     clr    -8(r2)
  376. /
  377.     mov    headsz,datadr
  378.     add    datasz,datadr
  379. /
  380.     mov    $frlist,r0
  381. 1:    clr    (r0)+
  382.     cmp    r0,$frend
  383.     blo    1b
  384.  
  385.     mov    hblk,r2
  386.     add    $hblk,r2
  387.     mov    (r2),hblk
  388.     clr    w(r2)
  389.     mov    headsz,a(r2)
  390.     mov    datadr,l(r2)
  391.     mov    datasz,r0
  392.     jsr    pc,log2
  393.     asl    r0
  394.     cmp    r0,$frend-frlist
  395.     blo    9f; 4; 9:
  396.     sub    $hblk,r2
  397.     mov    r2,frlist(r0)
  398. /
  399. /    install plausible pointers to make octal dumps look ok
  400. /
  401.     mov    $hblk,r1
  402. 1:    mov    (r1),r1
  403.     beq    1f
  404.     add    $hblk,r1
  405.     mov    headsz,a(r1)
  406.     mov    headsz,l(r1)
  407.     br    1b
  408. /
  409. 1:    mov    afout,r0
  410.     sys    write;hblk;hsz
  411.     jsr    pc,reset
  412.     mov    (sp)+,r2
  413.     mov    (sp)+,r0
  414.     rts    pc
  415. . = b1 + [512.*numb]
  416. /
  417. .bss
  418.  
  419. flag:    .=.+2
  420. stats:    .=.+18.
  421. useful:    .=.+2
  422. afi:    .=.+2
  423. afout:    .=.+2
  424. datadr:    .=.+2
  425. hblk: .=.+2    /must remain here - pointer to free header
  426. frlist: .=hblk+34.
  427. frend:
  428. headers:
  429. strbuf:    .=hblk+hsz
  430. strend:
  431. nchar: .=.+2
  432. end:
  433.