[SOLVED] Question about Kernighan and Ritchie chapter 5.4

amikoyan · 06-30-2022, 01:40 PM

I am trying to write a main function to use the storage allocator in chapter 5.4. of K&R (p101). The functions alloc(n) and afree(p) are from the book; the contents of int main() are my attempt to call them as the authors may have intended.

I have two questions:

1. Am I on the right track with how I have called alloc(n) and afree(p)?

2. As called here afree(p) does not release the storage. What have I done wrong?
How do I call the two functions so they work as intended?

Code:

#include <stdio.h>
#define ALLOCSIZE 10000 /* size of available space */
char *alloc(int n);
void afree(char *p);
int main() {
	
	char *p1, *p2, *p3;
	
	p1 = alloc(1);
	p2 = alloc(1);
	p3 = alloc(1);
	printf("p1 is at %p\n", p1);
	printf("p2 is at %p\n", p2);
	printf("p3 is at %p\n", p3);
	
	afree(p3);
	afree(p2);
	afree(p1);
	printf("p1 is at %p\n", p1);
	printf("p2 is at %p\n", p2);
	printf("p3 is at %p\n", p3);
	return 0;
	
}
static char allocbuf[ALLOCSIZE]; /*storage for alloc */
static char *allocp = allocbuf; /*next free position */

char *alloc(int n) {  /*return pointer to n characters */
		if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
			allocp += n;
			return allocp - n;/*old p */
		} else /* not enough room*/
			return 0;
		
}
void afree(char *p) {
	if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
		allocp = p;
	}

astrogeek · 06-30-2022, 02:11 PM

Quote:

Originally Posted by amikoyan

1. Am I on the right track with how I have called alloc(n) and afree(p)?

2. As called here afree(p) does not release the storage. What have I done wrong?
How do I call the two functions so they work as intended?

Yes, (on a quick look) you appear to be using alloc(n) and afree(p) as intended.

Why do you conclude that it does not release the "storage"? Probably because you are using p1, p2 and p3 as indicators but they have not been reset once the allocp pointer has been decremented.

Use allocp as what it is - pointer to the next free location and reset the other pointers once they have been freed. Untested example:

Code:

#include <stdio.h>
#define ALLOCSIZE 10000 /* size of available space */
static char allocbuf[ALLOCSIZE]; /*storage for alloc */
static char *allocp = allocbuf; /*next free position */
char *alloc(int n);
void afree(char *p);


int main() {
	
	char *p1, *p2, *p3;
	
	p1 = alloc(1);
	p2 = alloc(1);
	p3 = alloc(1);
	printf("p1 is at %p\n", p1);
	printf("p2 is at %p\n", p2);
	printf("p3 is at %p\n", p3);
	
	afree(p3); p3=0;
        printf("allocp is at %p\n", allocp);
	afree(p2); p2=0;
        printf("allocp is at %p\n", allocp);
	afree(p1); p1=0;
        printf("allocp is at %p\n", allocp);

	return 0;
	
}

char *alloc(int n) {  /*return pointer to n characters */
		if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
			allocp += n;
			return allocp - n;/*old p */
		} else /* not enough room*/
			return 0;
		
}
void afree(char *p) {
	if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
		allocp = p;
	}

UPDATE: Pulling my K&R off the shelf, I see that section 5.4 is really about pointer arithmetic, not memory allocators.

So it might be more informative to modify the above code something like this...

Code:

        printf("Free space is %d\n", allocbuf + ALLOCSIZE - allocp);
        afree(p3); p3=0;
        printf("Free space is %d\n", allocbuf + ALLOCSIZE - allocp);
        afree(p2); p2=0;
        printf("Free space is %d\n", allocbuf + ALLOCSIZE - allocp);
        afree(p1); p1=0;
        printf("Free space is %d\n", allocbuf + ALLOCSIZE - allocp);

You might want to add some corresponding lines between the calls to alloc(n) so that you can see the changes as space is allocated, an exercise I leave to you!

Good luck!

amikoyan · 06-30-2022, 02:53 PM

Quote:

Originally Posted by astrogeek

Why do you conclude that it does not release the "storage"? Probably because you are using p1, p2 and p3 as indicators but they have not been reset once the allocp pointer has been decremented.

Thank you for your help.
I was expecting the 'storage' to be released back to the original memory address and in my program this did not seem to be happening. However, in your version of the program I can see we return to 0x404060 - which is p1's address:

Code:

p1 is at 0x404060
p2 is at 0x404061
p3 is at 0x404062
allocp is at 0x404062
allocp is at 0x404061
allocp is at 0x404060

However, running splint gives these warnings, which seems to imply that the storage is not released:

Code:

Splint 3.1.2a --- Jun 16 2022

my_alloc.c: (in function main)
my_alloc.c:20:13: Fresh storage p3 (type char *) not released before
                     assignment: p3 = 0
  A memory leak has been detected. Storage allocated locally is not released
  before the last reference to it is lost. (Use -mustfreefresh to inhibit
  warning)
   my_alloc.c:15:2: Fresh storage p3 created
my_alloc.c:22:13: Fresh storage p2 (type char *) not released before
                     assignment: p2 = 0
   my_alloc.c:14:2: Fresh storage p2 created
my_alloc.c:24:13: Fresh storage p1 (type char *) not released before
                     assignment: p1 = 0
   my_alloc.c:13:2: Fresh storage p1 created
my_alloc.c: (in function alloc)
my_alloc.c:34:11: Unqualified static storage allocp - n returned as implicitly
                     only: allocp - n
  Static storage is transferred in an inconsistent way. (Use -statictrans to
  inhibit warning)
my_alloc.c:36:11: Null storage returned as non-null: 0
  Function returns a possibly null pointer, but is not declared using
  /*@null@*/ annotation of result.  If function may return NULL, add /*@null@*/
  annotation to the return value declaration. (Use -nullret to inhibit warning)
my_alloc.c:5:7: Function exported but not used outside my_alloc: alloc
  A declaration is exported, but not used outside this module. Declaration can
  use static qualifier. (Use -exportlocal to inhibit warning)
   my_alloc.c:38:1: Definition of alloc
my_alloc.c:6:6: Function exported but not used outside my_alloc: afree
   my_alloc.c:42:2: Definition of afree

Finished checking --- 7 code warnings

astrogeek · 06-30-2022, 03:03 PM

First, see my updated comments in previous post.

Splint is not aware of the "allocator" functions alloc(n) and afree(*p). It simply sees a pointer being cleared without a corresponding free(), assumes it was allocated elsewhere but never freed and issues the warning.

There is no actual memory leak because the buffer used as the memory pool by alloc() is a character array...

Code:

static char allocbuf[ALLOCSIZE];

... and remains the same size in real memory.

Put another way, real memory is only allocated for the array, whereas alloc() and afree() only set pointers into a pool of memory allocated elsewhere.

amikoyan · 06-30-2022, 03:22 PM

Thank you again,

I will follow your suggestion to add some corresponding lines between the calls to alloc(n) to see the changes as space is allocated.
The warnings from splint did concern me, but your explanation clears that up.

I will keep exploring this pair of functions, I have found them very interesting.

astrogeek · 06-30-2022, 03:34 PM

You are welcome!

Be sure not to become lost thinking those functions are about memory allocation! Remember that the thing being taught in that section is address arithmetic, or pointer arithmetic, and allocation from a pool of memory is just the illustrative example being given.

Good luck with your studies!

amikoyan · 07-01-2022, 01:50 AM

Quote:

Originally Posted by astrogeek

You are welcome!

Be sure not to become lost thinking those functions are about memory allocation! Remember that the thing being taught in that section is address arithmetic, or pointer arithmetic, and allocation from a pool of memory is just the illustrative example being given.

Yes, that is a perceptive comment, I had started thinking about the functions more in terms of memory allocation than address arithmetic. I will try to keep on track