Looking at this further, there are some more potentially problematic aspects:
First, the value of BLK_DATA_MULTI_OFFSET
under Glulx is currently 20, not 16, though I think that it may have once been defined as 16, as that’s what the documentation in Flex.i6t
says is the worst case.
Second, it seems like the issue above might have a bad interaction with routine FlexAllocate()
:
[ FlexAllocate size kov flags
dsize n m free_block min_m max_m smallest_oversized_block secondhalf i hsize head tail;
if (HeapMakeSpace(size, flags & BLK_FLAG_MULTIPLE) == false) FlexError("ran out"); ! what if too-small indicator on obtained block?
! Calculate the header size for a block of this KOV
if (flags & BLK_FLAG_MULTIPLE) hsize = BLK_DATA_MULTI_OFFSET;
else hsize = BLK_DATA_OFFSET;
! Calculate the data size
n=0; for (dsize=1: ((dsize < hsize+size) || (n<3+(WORDSIZE/2))): dsize=dsize*2) n++; ! dsize for size 8190 is 16384? / odd minimum calc
! Seek a free block closest to the correct size, but starting from the
! block after the fixed head-free-block, which we can't touch
min_m = 10000; max_m = 0;
for (free_block = Flex_Heap-->BLK_NEXT:
free_block ~= NULL:
free_block = free_block-->BLK_NEXT) {
m = free_block->BLK_HEADER_N; ! evaluates to too-small value for new block obtained by HeapMakeSpace()?
! Current block the ideal size
if (m == n) jump CorrectSizeFound;
! Current block too large: find the smallest which is larger than needed
if (m > n) {
if (min_m > m) {
min_m = m;
smallest_oversized_block = free_block;
}
}
! Current block too small: find the largest which is smaller than needed
if (m < n) { ! this case would apply to new block obtained?
if (max_m < m) {
max_m = m;
}
}
}
if (min_m == 10000) {
! Case I: No block is large enough to hold the entire size
if (flags & BLK_FLAG_MULTIPLE == 0) FlexError("too fragmented"); ! this case would apply to new block obtained? ! LAST COMMENT
! Set dsize to the size in bytes if the largest block available
for (dsize=1: max_m > 0: dsize=dsize*2) max_m--;
! Split as a head (dsize-hsize), which we can be sure fits into one block,
! plus a tail (size-(dsize-hsize), which might be a list of blocks
head = FlexAllocate(dsize-hsize, kov, flags);
if (head == 0) FlexError("for head block not available");
tail = FlexAllocate(size-(dsize-hsize), kov, flags);
if (tail == 0) FlexError("for tail block not available");
head-->BLK_NEXT = tail;
tail-->BLK_PREV = head;
return head;
}
! Case II: No block is the right size, but some exist which are too big
! Set dsize to the size in bytes of the smallest oversized block
for (dsize=1,m=1: m<=min_m: dsize=dsize*2) m++;
free_block = smallest_oversized_block;
while (min_m > n) {
! Repeatedly halve free_block at the front until the two smallest
! fragments left are the correct size: then take the frontmost
dsize = dsize/2;
! print "Halving size to ", dsize, "^";
secondhalf = free_block + dsize;
secondhalf-->BLK_NEXT = free_block-->BLK_NEXT;
if (secondhalf-->BLK_NEXT ~= NULL)
(secondhalf-->BLK_NEXT)-->BLK_PREV = secondhalf;
secondhalf-->BLK_PREV = free_block;
free_block-->BLK_NEXT = secondhalf;
free_block->BLK_HEADER_N = (free_block->BLK_HEADER_N) - 1;
secondhalf->BLK_HEADER_N = free_block->BLK_HEADER_N;
secondhalf-->BLK_HEADER_KOV = free_block-->BLK_HEADER_KOV;
secondhalf-->BLK_HEADER_RCOUNT = 0;
secondhalf->BLK_HEADER_FLAGS = free_block->BLK_HEADER_FLAGS;
min_m--;
}
! Once that is done, free_block points to a block which is exactly the
! right size, so we can fall into...
! Case III: There is a free block which has the correct size.
.CorrectSizeFound;
! Delete the free block from the double linked list of free blocks: note
! that it cannot be the head of this list, which is fixed
if (free_block-->BLK_NEXT == NULL) {
! We remove final block, so previous is now final
(free_block-->BLK_PREV)-->BLK_NEXT = NULL;
} else {
! We remove a middle block, so join previous to next
(free_block-->BLK_PREV)-->BLK_NEXT = free_block-->BLK_NEXT;
(free_block-->BLK_NEXT)-->BLK_PREV = free_block-->BLK_PREV;
}
free_block-->BLK_HEADER_KOV = KindAtomic(kov);
free_block-->BLK_HEADER_RCOUNT = 1;
free_block->BLK_HEADER_FLAGS = flags;
if (flags & BLK_FLAG_MULTIPLE) {
free_block-->BLK_NEXT = NULL;
free_block-->BLK_PREV = NULL;
}
! Zero out the data bytes in the memory allocated
for (i=hsize:i<dsize:i++) free_block->i=0;
return free_block;
];
Looking over the commented lines above (ending with LAST COMMENT
), it seems as though the freshly-obtained but mislabeled new free block would not meet the size requirement calculated for dsize
, e.g. 16384 for a requested size
parameter of 8190. (Note that in this routine the size
parameter means still seems to mean the number of bytes requested for data storage.) Wouldn’t this mean that the routine will see no satisfactory blocks available and respond with a “too fragmented
” RTE?
Third, the way that a minimum value for dsize
is calculated, the expression
(n<3+(WORDSIZE/2))
evaluates to 4 (i.e. 2^4 = 16) for Z-Machine and 5 (i.e. 2^5 = 32) for Glulx. These are fine at present, but they don’t seem future-proof in the event of further changes to the block header. Something like:
n=0; for (dsize=1: ((dsize < hsize+size) || (IncreasingPowersOfTwo_TB-->n < (BLK_DATA_MULTI_OFFSET+WORDSIZE))): dsize=dsize*2) n++;
might do the trick?
EDIT: Logic adjusted so that minimum size is governed by BLK_DATA_MULTI_OFFSET+WORDSIZE
because any free block resulting from a split will need to be a multiple block of the same size, even if a single block is being requested. On Z-Machine, it’s possible to fit a 1-word short block into a block of size 8, but it’s not possible to fit the multiple block header into a block of size 8, so splitting a free size 16 block isn’t possible under the existing system.