By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,916 Members | 1,316 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,916 IT Pros & Developers. It's quick & easy.

Limiting Recursion Selectively

P: n/a
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
Nov 13 '05 #1
Share this Question
Share on Google+
11 Replies


P: n/a
Michael B Allen wrote:

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
Nov 13 '05 #2

P: n/a
pete wrote:

Michael B Allen wrote:

Here's fragment of C from an allocator. So how can I limit this recursive call? Does any else have a simple solution to
limit this recursive call in the way I've described?
} while ((can't find memory) && 2 > ++reclaim);


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

--
pete
Nov 13 '05 #3

P: n/a
Michael B Allen wrote:

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;
}

--
Er*********@sun.com
Nov 13 '05 #4

P: n/a
On Tue, 28 Oct 2003 05:23:04 -0500, Michael B Allen wrote:
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
Nov 13 '05 #5

P: n/a
On Tue, 28 Oct 2003 10:58:15 -0500, Eric Sosman wrote:
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.
<snip>
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
Nov 13 '05 #6

P: n/a
Michael B Allen wrote:

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!

--
Er*********@sun.com
Nov 13 '05 #7

P: n/a
On Tue, 28 Oct 2003 16:18:45 -0500, Michael B Allen wrote:
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?

Nov 13 '05 #8

P: n/a
On Tue, 28 Oct 2003 20:23:31 -0500, Sheldon Simms wrote:
On Tue, 28 Oct 2003 16:18:45 -0500, Michael B Allen wrote:
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?


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
Nov 13 '05 #9

P: n/a
On Wed, 29 Oct 2003 03:20:01 -0500, Michael B Allen wrote:
On Tue, 28 Oct 2003 20:23:31 -0500, Sheldon Simms wrote:
On Tue, 28 Oct 2003 16:18:45 -0500, Michael B Allen wrote:
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?


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

Nov 13 '05 #10

P: n/a
On Wed, 29 Oct 2003 11:11:41 -0500, Sheldon Simms wrote:
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
Nov 13 '05 #11

P: n/a
On Wed, 29 Oct 2003 14:37:07 -0500, Michael B Allen wrote:
On Wed, 29 Oct 2003 11:11:41 -0500, Sheldon Simms wrote:
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;


I didn't claim that my code was correct. :-)
Nov 13 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.