%%off % Section 2.5, Algorithm A : First-Fit Method % Author Chan Vinh VONG % Draft Version 2012 April 8th % Edited September 2012 by Martin Ruckert % % Notes: % - the block header must fit in one OCTA otherwise requesting a block % of one OCTA would lead to the allocation of the entire block header % i.e more than one OCTA; e.g if the header block is made of 2 OCTAs, % one for LINK and the other for SIZE then if requesting N = 1 when % SIZE = 2, then the entire block header must be freed, thus we % introduced one unallocated and unreachable OCTA; % - memory is segmented anyway, so using one full OCTA for LINK would % be quite an overengineered solution. % % Henceforth, we use the following data structure for a block header: % % TETRA TETRA % +--------+--------+ % | SIZE | LINK | % +--------+--------+ % % - a negative LINK is a NULL address, hence LINK is effectively on 31 % bits % - LINK is a relative address to the start of a 8*(2^31-1) byte sized % area in memory dedicated to allocation/pooling; thus, the value of % LINK is the number of OCTAs to be added to the base address, % - 2^31-1 OCTAs is 16G, sounds reasonable % - managing more memory would just require an entry directory for % dispcatching to multiple 16G segments; the overhead may be of about % 2 or 3 OCTAs per such 16G segments, which is more than affordable % (one may store the total available size of the segment in an entry % in order to speed up the next request or give some priority so that % allocation is spread evenly in all segments), % - SIZE indicates how many OCTAs are available (because LINK is octa- % aligned, byte-level allocation would lead to wasted bytes). % % Calling Sequence: % $1 <- N, number of OCTAs requested % PUSHJ $0,FFM % % Exit Conditions: % return address of requested block, else -1 if the program could % not allocate memory % % Global Variables: % :LOC_AVAIL pointer to the link variable AVAIL which is the first % available block in memory, AVAIL is a relative address % like LINK % :BASE base address of the memory pool % PREFIX FFM: n IS $0 % requested number of OCTAs P IS $1 Q IS $2 s IS $3 k IS $4 %%on :Allocate SET P,:LOC_AVAIL %%% 1H SET Q,P LDT P,Q,4 BN P,8F $P < 0$? %%% 8ADDU P,P,:BASE LDTU s,P,0 Is the block big enough? SUB k,s,n BN k,1B $k \ge 0$ ? %%% 8ADDU $0,k,P Return value is $P+8k$. BNZ k,3F Jump if $k\ne 0$. LDT P,P,4 Remove block. STT P,Q,4 POP 1,0 %%% 3H STTU k,P,0 Update block. POP 1,0 %%% 8H NEG $0,1 POP 1,0 %%off PREFIX :