Limiting Recursion Selectively

[Michael B Allen]

Here's fragment of C from an allocator. This allocator permits the user
to specify a callback to reclaim memory if necessary. If memory cannot be
found the 'if (reclaim)' block is entered and the callback is called.

However, I would like to implement some kind of barrier that prevents the
callback from calling suba_alloc recusively. One recursive call is ok,
but if memory isn't found a second time, chances are good an infinate
loop will occur.

So how can I limit this recursive call? Below I have devised a method of
saving the address of an object on the first call reasoning that
subsiquent calls cannot reuse the same address but this is a poor
solution as it is difficult to reset the reclaim_barrier to NULL.

Does any else have a simple solution to limit this recursive call in the
way I've described?

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrier == NULL) {
suba->reclaim_barrier = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrier != &reclaim ||
suba->reclaim(suba, suba->reclaim_arg, reclaim) == 0) {
errno = ENOMEM;
return NULL;
}
}

if (can't find memory) {
reclaim++;
goto again;
}

return the memory;
}

Thanks,
Mike

 

[pete]

Here's fragment of C from an allocator. This allocator permits the user
to specify a callback to reclaim memory if necessary. If memory cannot be
found the 'if (reclaim)' block is entered and the callback is called.

However, I would like to implement some kind of barrier that prevents the
callback from calling suba_alloc recusively. One recursive call is ok,
but if memory isn't found a second time, chances are good an infinate
loop will occur.

So how can I limit this recursive call? Below I have devised a method of
saving the address of an object on the first call reasoning that
subsiquent calls cannot reuse the same address but this is a poor
solution as it is difficult to reset the reclaim_barrier to NULL.

Does any else have a simple solution to limit this recursive call in the
way I've described?

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrier == NULL) {
suba->reclaim_barrier = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrier != &reclaim ||
suba->reclaim(suba, suba->reclaim_arg, reclaim) == 0) {
errno = ENOMEM;
return NULL;
}
}

if (can't find memory) {
reclaim++;
goto again;
}

return the memory;
}

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

do {
if (suba->reclaim_barrier == NULL) {
suba->reclaim_barrier = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrier != &reclaim
||
suba->reclaim(suba, suba->reclaim_arg, reclaim) == 0) {
errno = ENOMEM;
return NULL;
}
} while ((can't find memory) && 2 > ++reclaim);

return the memory;
}

 

[pete]

} while ((can't find memory) && 2 > ++reclaim);

Sorry about that.
I think the problem is more complicated,
than what I was thinking about.

 

[Eric Sosman]

Here's fragment of C from an allocator. This allocator permits the user
to specify a callback to reclaim memory if necessary. If memory cannot be
found the 'if (reclaim)' block is entered and the callback is called.

However, I would like to implement some kind of barrier that prevents the
callback from calling suba_alloc recusively. One recursive call is ok,
but if memory isn't found a second time, chances are good an infinate
loop will occur.

So how can I limit this recursive call? Below I have devised a method of
saving the address of an object on the first call reasoning that
subsiquent calls cannot reuse the same address but this is a poor
solution as it is difficult to reset the reclaim_barrier to NULL.

Does any else have a simple solution to limit this recursive call in the
way I've described?

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrier == NULL) {
suba->reclaim_barrier = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrier != &reclaim ||
suba->reclaim(suba, suba->reclaim_arg, reclaim) == 0) {
errno = ENOMEM;
return NULL;
}
}

if (can't find memory) {
reclaim++;
goto again;
}

return the memory;
}

Could you make the `reclaim_barrier' be a simple depth
counter instead of an address? (And could you consider
getting rid of the `goto'?)

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
void *new;
int rc;

while ((new = get_some_memory(...)) == NULL) {
if (suba->reclaim_depth >= RECLAIM_MAX_DEPTH)
break;
++suba->reclaim_depth;
rc = suba_reclaim(...);
--suba->reclaim_depth;
if (rc == 0)
break;
}
if (new == NULL)
errno = ENOMEM;
return new;
}

 

[Sheldon Simms]

Here's fragment of C from an allocator. This allocator permits the user
to specify a callback to reclaim memory if necessary. If memory cannot be
found the 'if (reclaim)' block is entered and the callback is called.

However, I would like to implement some kind of barrier that prevents the
callback from calling suba_alloc recusively. One recursive call is ok,
but if memory isn't found a second time, chances are good an infinate
loop will occur.

I don't see any recursive calls in your code at all. As far as I
can tell, what you are trying to do in suba_alloc() is this:

1. Find some free memory to return. If you find it, return it.
2. If you can't find any free memory, allow the user the opportunity
to free up some space. This is done by calling a user function.
3. Having called the user function, go back to step one and look
for free memory.

Your problem is that the loop could possibly infinite, right? If
this is the case then Pete gave you the right answer, limit this
iteration with a counter variable:

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int count;
unsigned char * mem = NULL;
/* mem will point to allocated memory */

for (count = 0; count < 2; ++count)
{
/* try to find memory */

if (can't find memory)
{
if (suba->reclaim == NULL)
break;
if (suba->reclaim(suba, suba->reclaim_arg) == 0)
break;
}
}

if (mem == NULL)
my_errno = ENOMEM;
else
; /* do any preparation needed before returning the memory */

return mem;
}

If you really are worried about recursive calls -- for example, if the
function suba->reclaim() might call suba_alloc() (although I don't
see how that would be useful or why it would be necessary), then you
could add a member in struct allocator that counts how many times
suba_alloc() is called.

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int count;
unsigned char * mem = NULL;
/* mem will point to allocated memory */

/* has suba_alloc() been called recursively too often? */
if (suba->call_count < 2)
{
/* count this call to suba_alloc() */
suba->call_count += 1;

for (count = 0; count < 2; ++count)
{
/* try to find memory */

if (can't find memory)
{
if (suba->reclaim == NULL)
break;

if (suba->reclaim(suba, suba->reclaim_arg) == 0)
break;
}
}
}

if (mem == NULL)
my_errno = ENOMEM;
else
; /* do any preparation needed before returning the memory */

/* all done, clear call count */
suba->call_count = 0;
return mem;
}

-Sheldon

 

[Michael B Allen]

Could you make the `reclaim_barrier' be a simple depth
counter instead of an address? (And could you consider getting rid of
the `goto'?)

void *
suba_alloc(struct allocator *suba, size_t size, int zero) {
void *new;
int rc;

while ((new = get_some_memory(...)) == NULL) {
if (suba->reclaim_depth >= RECLAIM_MAX_DEPTH)
break;
++suba->reclaim_depth;
rc = suba_reclaim(...);
--suba->reclaim_depth;
if (rc == 0)
break;
}
if (new == NULL)
errno = ENOMEM;
return new;
}

Well I used goto because there are actually two places where "can't find
memory" can occur so I felt the goto was the least intrusive way to deal
with this exceptional condition. I would also rather not use a function
call in the default path (get_some_memory) to deal with an exceptional
case and the alternative would be to have a copy of while body in two
places. So for the moment I think I prefer the goto. I'm not offended by
goto really but I use it very selectively in obviously correct situations.

Your depth counter is definately the way to go though. My example and
Sheldon's suggestion fail when a recursive call "can't find memory"
because it reset's the counter/barrier. Incrementing before the call and
then decrementing after handles this properly and has the added benefit
of being able to define the limit (RECLAIM_DEPTH_MAX).

void *
suba_alloc(struct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
int progress = 0;

if (suba->reclaim && suba->reclaim_depth <= RECLAIM_DEPTH_MAX) {
suba->reclaim_depth++;
progress = suba->reclaim(suba, suba->reclaim_arg, reclaim);
suba->reclaim_depth--;
}

if (!progress) {
errno = ENOMEM;
return NULL;
}
}

...
if (can't find memory) {
reclaim++;
goto again;
}
...
if (can't find memory here either) {
reclaim++;
goto again;
}

BTW: What's with the precrementing (e.g. ++suba->reclaim_depth)?

Mike

 

[Eric Sosman]

BTW: What's with the precrementing (e.g. ++suba->reclaim_depth)?

Premature optimization. When I started rearranging the code
I was thinking of something like

if (suba->reclaim_depth++ >= LIMIT ...)

.... and then some bad old habits kicked in and I "optimized"
this to

if (++suba->reclaim_depth > LIMIT ...)

.... and then I wound up not using such an `if' anyhow. P.O.
truly *is* the R.O.A.E., as Knuth has told us. Sorry!

 

[Sheldon Simms]

Your depth counter is definately the way to go though. My example and
Sheldon's suggestion fail when a recursive call "can't find memory"
because it reset's the counter/barrier. Incrementing before the call and
then decrementing after handles this properly and has the added benefit
of being able to define the limit (RECLAIM_DEPTH_MAX).

Would you mind explaining where the recursive call is being made
and why? Are you expecting the function pointed to by suba->reclaim
to call suba_alloc() itself?

 

[Michael B Allen]

Would you mind explaining where the recursive call is being made and
why? Are you expecting the function pointed to by suba->reclaim to call
suba_alloc() itself?

Yes, because suba->reclaim is a user defined function there is no
guaruntee that it would not attempt to call suba_alloc(). And that
would not be unreasonable. Consider a network server that allocates
memory for each client connected. The reclaim function could shutdown
some clients to release memory but it might need a little more memory
to send a "you've been logged off" message to the client. If the size of
the memory requested in the recursive call is smaller than the original
memory requested, or if the reclaim function managed to release some
memory before calling suba_alloc, it's reasonable to assume that the
recursive call could succeed. And that might be important as you might
otherwise be prone to deacdlock in low-memory situations.

It's a very nice mechanism actually [1]. I wish the standard library
implementation had it.

Mike

1. Inspired by the "natrual tension" description in "The Slab Allocator:
An Object-Caching Kernel Memory Allocator" by Jeff Bonwick Sun
Microsystems, 1994
http://citeseer.nj.nec.com/bonwick94slab.html

 

[Sheldon Simms]

Yes, because suba->reclaim is a user defined function there is no
guaruntee that it would not attempt to call suba_alloc(). And that
would not be unreasonable. Consider a network server that allocates

Ok. I understand now. Your original post wasn't clear on this.
By the way, the second version of the code I gave used a call-depth
indicator as well, only I put it in the struct allocator.
Furthermore, those gotos really aren't necessary in this case.

-Sheldon

 

[Michael B Allen]

Ok. I understand now. Your original post wasn't clear on this.
Sorry!

By the
way, the second version of the code I gave used a call-depth indicator
as well, only I put it in the struct allocator.

Consider your code in the following scenario;

suba->call_count = 0
call suba_alloc
call_count += 1
can't find memory
call reclaim
call suba_alloc
call_count is 1 which is < 2
call_count += 1
can't find memory
call reclaim
return 0
reset call_count = 0 <==== bad
return NULL
call suba_alloc
call_count is 0 which is < 2
call_count += 1;
can't find memory
call reclaim
call suba_alloc
call_count is 1 which is < 2
can't find memory
call reclaim
return 0
reset call_count = 0 <==== bad
return NULL
call suba_alloc
call_count is 0 which is < 2
....

Mike

 

[Sheldon Simms]

Consider your code in the following scenario;

I didn't claim that my code was correct.