Index out of range in Engine.sc

Hi

Shouldn’t that line read:

^array[temp.start + (temp.size - 1) - addrOffset]

? It can go out of range by 1 and return nil.

AFAICS it’s ok if it returns nil.

Probably we should deprecate findNext and findPrevious and rename them to prFindNext/Previous. It’s been awhile ago so I might have forgotten something, but I can’t think of a good reason why a user would call findNext. You should get a concrete number from alloc and not findNext. (All of the uses of findNext/Previous are guarded by a notNil if-construct, so I think nil is an expected possible return value.)

For that matter, there’s no guarantee that a ContiguousBlockAllocator will return an index. It may have run out of indices to allocate.

hjh

Actually the explanation is a little different.

The size there is a block size, not the array size.

Let’s say you’ve allocated 2 indices, starting at 0.

Then the array should contain:

  • array[0]: ContiguousBlock(0, 2, true) – true = used
  • array[1]: (I think) nil at this time
  • array[2]: ContiguousBlock(2, allocatorSize-2, false)

allocator.findNext(0) is then supposed to find the next block (whether used or not) after 0.

If there already exists a block at 0, then the next array entry should be at block index start+size – so there’s no need to do a linear-time search – it’s faster to return the item just beyond this block’s boundary. (Or, if this is the last block, then there is no next block and nil is the correct answer.)

In general, you’re right that + size is a red flag for array access – but that assumes that the size is the array’s size. That’s not the case here.

hjh

I don’t have the code right now but there is a case when allocating/deallocating all available single channel buses in which the array returns nil because it is out of range (I regret not saving it), the return value is ok but it may leave one bus as not available. I’ll try to reproduce the case.

That would be helpful. I can’t reproduce it.

c = ContiguousBlockAllocator(3);

c.debug;

// Array:
// 0: ContiguousBlock(0, 3, false)
// 
// Free sets:
// ^^ empty here means one of two things:
// - no index has ever been 'free'd (initial case)
// - all previously freed indices have been reallocated

a = Array.fill(3, { c.alloc });

c.debug;

// Array:
// 0: ContiguousBlock(0, 1, true)
// 1: ContiguousBlock(1, 1, true)
// 2: ContiguousBlock(2, 1, true)  // all slots are busy ('true'), OK
// 
// Free sets:

c.free(a[1]);
c.debug;

// Array:
// 0: ContiguousBlock(0, 1, true)
// 1: ContiguousBlock(1, 1, false)
// 2: ContiguousBlock(2, 1, true)
// 
// Free sets:
// 1: IdentitySet[ ContiguousBlock(1, 1, false) ]

c.free(a[2]);
c.debug;

// Array:
// 0: ContiguousBlock(0, 1, true)
// 1: ContiguousBlock(1, 2, false)
// 
// Free sets:

b = c.alloc;  // '1' -- no previously freed, so it uses the top unused element
c.debug;

// Array:
// 0: ContiguousBlock(0, 1, true)
// 1: ContiguousBlock(1, 1, true)
// 2: ContiguousBlock(2, 1, false)
// 
// Free sets:

c.alloc;  // 2
c.debug;

// Array:
// 0: ContiguousBlock(0, 1, true)
// 1: ContiguousBlock(1, 1, true)
// 2: ContiguousBlock(2, 1, true)
// 
// Free sets:

At no point in this sequence is c's state inconsistent. There must be something in your case other than single channels perhaps?

hjh

Here:

  • set this debug posts after var temp = … in findNext

“*** % % %”.format(temp.start, temp.size, addrOffset).postln;
“*** %”.format(array[temp.start + temp.size - addrOffset]).postln;

recompile and then:

s.options.numControlBusChannels = 64;
s.boot(); // needed to update allocators.
b = 64.collect({ Bus.control });
b.do({ arg i; i.free() });

It sould post:

*** 0 1 0
*** ContiguousBlock(1, 1, true)
*** 0 2 0
*** ContiguousBlock(2, 1, true)

*** 0 64 0
*** nil

Last postln is nil because the index is out of range.

It just happens that also the content of the array is all nil except for the first position but the index goes out of range for sure, then, what happens with the object in the first position if is never touched?

But that doesn’t matter. What matters is the final state of the allocator.

s.options.numControlBusChannels = 64;
s.boot;

c = Array.fill(64, { Bus.control(s, 1) });

s.controlBusAllocator.debug;

// state:
Array:
0: ContiguousBlock(0, 1, true)
1: ContiguousBlock(1, 1, true)
2: ContiguousBlock(2, 1, true)
3: ContiguousBlock(3, 1, true)
... snip
62: ContiguousBlock(62, 1, true)
63: ContiguousBlock(63, 1, true)

Free sets:

// ^^ correct


c.do(_.free);

s.controlBusAllocator.debug;

Array:
0: ContiguousBlock(0, 64, false)

Free sets:

The final state is: All control bus indices have been reclaimed.

Let’s check it: after that, allocate 64 again.

c = Array.fill(64, { Bus.control(s, 1) });

// no failures

c.any(_.isNil)
-> false  // no nil entries

There’s no bug here.

findNext is private. It does nothing of use, and reports nothing of use, to the end user.

hjh

Ok, I was wondering about that. Maybe is not optimal to have internal code that uses the indices like that, it leaves people/maintainers thinking why.

I agree with you that the code is unnecessarily hard to read and understand. I can submit a fix for that later.

Certainly the line that you highlighted needs a comment to explain why nil is legitimate as a return value.

I’m working on a quick PR to update the code style and comments for the next release.

Thanks for pointing it out! Clearer code style will be an improvement and pay off some technical debt.

hjh

This should make it easier for others in the future:

hjh