Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I am having trouble conceptually understanding what is going on towards the end of this system call, and why. I understand the getstk.c method returns the highest memory address of available space, but don't understand what some of the code is doing. Some clarity on this would be great. The areas of code I don't fully understand are emphasized in asterisks.

/* getstk.c - getstk */

#include <xinu.h>

/*------------------------------------------------------------------------
 *  getstk  -  Allocate stack memory, returning highest word address
 *------------------------------------------------------------------------
 */
char    *getstk(
          uint32        nbytes          /* size of memory requested     */
        )
{
        intmask mask;                   /* saved interrupt mask         */
        struct  memblk  *prev, *curr;   /* walk through memory list     */
        struct  memblk  *fits, *fitsprev; /* record block that fits     */

        mask = disable();
        if (nbytes == 0) {
                restore(mask);
                return (char *)SYSERR;
        }

        nbytes = (uint32) roundmb(nbytes);      /* use mblock multiples */

        prev = &memlist;
        curr = memlist.mnext;
        fits = NULL;
        fitsprev = NULL;  /* to avoid a compiler warning */

        while (curr != NULL) {                  /* scan entire list     */
                if (curr->mlength >= nbytes) {  /* record block address */
                        fits = curr;            /*   when request fits  */
                        fitsprev = prev;
                }
                prev = curr;
                curr = curr->mnext;
        }

        if (fits == NULL) {                     /* no block was found   */
                restore(mask);
                return (char *)SYSERR;
        }
        if (nbytes == fits->mlength) {          /* block is exact match */
                fitsprev->mnext = fits->mnext;
        **} else {                                /* remove top section   */
                fits->mlength -= nbytes;
                fits = (struct memblk *)((uint32)fits + fits->mlength);
        }**
        memlist.mlength -= nbytes;
        restore(mask);
        **return (char *)((uint32) fits + nbytes - sizeof(uint32));**
}

The struct memblk can be found here:

struct  memblk  {           /* see roundmb & truncmb    */
    struct  memblk  *mnext;     /* ptr to next free memory blk  */
    uint32  mlength;        /* size of blk (includes memblk)*/
    };
extern  struct  memblk  memlist;    /* head of free memory list */

Why are they returning the fits + nbytes - sizeof(uint32)? Why are they casting fits(a struct) to type uint32?

share|improve this question

closed as off topic by jasonwryan, Stéphane Chazelas, Ulrich Dangel, goldilocks, manatwork Apr 27 '13 at 13:20

Questions on Unix & Linux Stack Exchange are expected to relate to Unix or Linux within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
It's actually not super relevant where this code came from, as long as there is a bit of general context ("this is memory management code"), which is why people recommended this get moved to Stack Overflow. Your question has more to do with C programming than any particular operating system, even if the code is from an OS kernel. –  goldilocks Apr 27 '13 at 12:59

1 Answer 1

These are the two scenarios where a block of sufficient size has been found. Notice in the first case, we are removing an entire node (fits) from memlist by linking the previous node's next pointer to the next pointer of this node. This block is then used in the return value, so I presume from that and the comments, etc. that the intent here is to find some free memory in a pool and remove it from the free pool for use.

    if (nbytes == fits->mlength) {          /* block is exact match */
            fitsprev->mnext = fits->mnext;
    **} else {                                /* remove top section   */
            fits->mlength -= nbytes;
            fits = (struct memblk *)((uint32)fits + fits->mlength);
    }**

Now, in the second case which you highlight, the block found is more than big enough. It's important that this entire thing not be returned because the excess will be wasted, and further, the nature of the return value (see below) implies that the receiver will have no record of the real size, which may mean if this block is reclaimed later, it could only be reclaimed on the basis of the requested size (the original value of parameter nbytes), walling off that wasted excess permanently in the mem pool.

To deal with this, the fits block is shortened to the length of the remainder. That is, not the length of the requested block, but the amount that will be left over when the requested amount is subtracted from the length of the found (more than big enough) block. Unlike in the first clause of the if/else, the fits block here is not removed from the pool. It is just shortened:

 fits->mlength -= nbytes;

Then the pointer, which will be used in the return value, is moved forward to the end of the newly shortened block. This points to the region that will be removed from the pool:

 fits = (struct memblk *)((uint32)fits + fits->mlength);

Notice that although the fits pointer was moved, the code does not bother to correct fits->mlength to the size of the region fits now points to (which is not the same as where it was on the previous line). This is because what is returned is not a struct. I would guess this function is called from somewhere which does not use struct memblk at all. In other words, struct memblk is used in this code, but not in the caller. So you could consider getstk() like a public API call, wherein struct memblk is not part of the public API -- it is just part of the internal mechanics.

The return value is just a char pointer, to the top (highest point) of a memory region.

getstk  -  Allocate stack memory, returning highest word address

Presumably, the caller is going to assume the pointer returned points to the top of a region nbytes in size. This is very similar to what malloc() does, eg:

char *dataA = malloc(4096);
char *dataB = getstk(4096);

Except that malloc returns an address at the bottom of a 4096 byte block, so the addresses will range from dataA to dataA + 4095. Since getstk() returns the high address, the range there will be from dataB - 4095 to dataB (actually, not quite, since "word size" is being used, keep reading).

Thus:

    return (char *)((uint32) fits + nbytes - sizeof(uint32));

This is the region nbytes long that fits currently points to the bottom of (what we'd normally consider the starting address, as with malloc). But getstk() is supposed to return the high address -- more accurately the highest word address. A "word" is usually 4 bytes/32 bits; here it is explicitly sizeof(uint32). So the address returned points to the last 4 bytes in a block nbytes in size (actually, nbytes was rounded via roundmb(), but presumably this system is also used in reclamation).

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.