473,662 Members | 2,546 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Limiting Recursion Selectively

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(stru ct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrie r == NULL) {
suba->reclaim_barrie r = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrie r != &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
11 1885
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(stru ct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrie r == NULL) {
suba->reclaim_barrie r = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrie r != &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(stru ct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

do {
if (suba->reclaim_barrie r == NULL) {
suba->reclaim_barrie r = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrie r != &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
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
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(stru ct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

again:
if (reclaim) {
if (suba->reclaim_barrie r == NULL) {
suba->reclaim_barrie r = &reclaim;
}
if (suba->reclaim == NULL || suba->reclaim_barrie r != &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_barrie r' be a simple depth
counter instead of an address? (And could you consider
getting rid of the `goto'?)

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

while ((new = get_some_memory (...)) == NULL) {
if (suba->reclaim_dept h >= RECLAIM_MAX_DEP TH)
break;
++suba->reclaim_dept h;
rc = suba_reclaim(.. .);
--suba->reclaim_dept h;
if (rc == 0)
break;
}
if (new == NULL)
errno = ENOMEM;
return new;
}

--
Er*********@sun .com
Nov 13 '05 #4
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(stru ct 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(stru ct 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
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_barrie r' be a simple depth
counter instead of an address? (And could you consider getting rid of
the `goto'?)

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

while ((new = get_some_memory (...)) == NULL) {
if (suba->reclaim_dept h >= RECLAIM_MAX_DEP TH)
break;
++suba->reclaim_dept h;
rc = suba_reclaim(.. .);
--suba->reclaim_dept h;
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_memor y) 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(stru ct allocator *suba, size_t size, int zero)
{
int reclaim = 0;

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

if (suba->reclaim && suba->reclaim_dept h <= RECLAIM_DEPTH_M AX) {
suba->reclaim_depth+ +;
progress = suba->reclaim(suba , suba->reclaim_arg, reclaim);
suba->reclaim_dept h--;
}

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
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_dept h > 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
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
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
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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
3415
by: Peri | last post by:
I'm trying to create Python parser/interpreter using ANTLR. Reading grammar from language refference I found: or_expr::= xor_expr | or_expr "|" xor_expr For me it looks like infinite recursion. And so it says ANTLR. Maybe I don't understand EBNF notation. For me it should look like this. or_expr::= xor_expr | xor_expr "|" xor_expr and in ANTLR grammar file like this:
12
2749
by: da Vinci | last post by:
Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted in modern day applications. Should we readily use it when we can or only when absolutly forced to use it?
43
4149
by: Lorenzo Villari | last post by:
I've tried to transform this into a not recursive version but without luck... #include <stdio.h> void countdown(int p) { int x;
10
14360
by: Robert Jacobson | last post by:
Hi, I'm develing a COM add-in for Microsoft Word XP that displays a form. I'd like to have the form display using the Windows XP theme. However, neither using a manifest nor calling Application.EnableVisualStyles does the trick. (EnableVisualStyles works but massive instability, probably because the system is trying to theme the Word application itself.) I'm now trying to selectively enable the themes for just my form, or just...
2
1562
by: Csaba Gabor | last post by:
I suppose spring fever has hit at alt.math.undergrad since I didn't get any rise from them when I posted this a week ago, so I am reposting this to some of my favorite programming groups: I'm looking for problems that have double (or more) recursion, where the split is not clean (ie. where there may be overlap). Let's call this overlapped recursion, where the
75
5602
by: Sathyaish | last post by:
Can every problem that has an iterative solution also be expressed in terms of a recursive solution? I tried one example, and am in the process of trying out more examples, increasing their complexity as I go. Here's a simple one I tried out: #include<stdio.h> /* To compare the the time and space cost of iteration against
19
2276
by: Kay Schluehr | last post by:
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/496691
20
2986
by: athar.mirchi | last post by:
..plz define it.
35
4715
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
8432
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8344
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
8546
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8633
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
6186
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5654
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4180
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
2762
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
1993
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.