Interpreting mem_map init code

[zolli]

Hi,

This question is about a piece of Linux kernel code, but is in fact a C
language question. I was looking throught some memory map init code and
ran into the following:

p = mem_map + MAP_NR(end_mem) ;
(*) start_mem = ((unsigned long)p + sizeof(long) - 1) &
~(sizeof(long)-1);

(*) This is the line I don't understand.

Where MAP_NR is defined (on an i386, anyway) as:

#define MAP_NR(addr) (__pa(addr) >> 12)
#define __pa(x) ((unsigned long)(x)-0xC0000000)

The first line sets p to the beginning of the heap plus the size of the
memory map which is calculated using the MAP_NR macro.

Using reasonable (?) example values if I do this:

unsigned long start_mem, end_mem, mem_map, p;

start_mem = 0xC1000000;
end_mem = 0xC2000000;
mem_map = start_mem;

p = mem_map + MAP_NR(end_mem) ;
start_mem = ((unsigned long)p + sizeof(long) - 1) &
~(sizeof(long)-1);
printf("p: 0x%x\n",p);
printf("start_m em: 0x%x\n",start_m em);

I get this as output:

p: 0xc1002000
start_mem: 0xc1002000

So what does the (*) line of code above do? I know that it changes
start_mem to the point where the memory allocated for the memory map
ends, but wouldn't that be more easily accomplished by:

start_mem += MAP_NR(end_mem) ;

My guess is that the line of code somehow sets the size of the mem_map
according to free memory minus the size of the mem_map, but I don't see how.

Thanks in advance,
zolli

[CBFalconer]

Re: Interpreting mem_map init code

zolli wrote:[color=blue]
>
> This question is about a piece of Linux kernel code, but is in
> fact a C language question. I was looking throught some memory
> map init code and ran into the following:
>
> p = mem_map + MAP_NR(end_mem) ;
> (*) start_mem = ((unsigned long)p + sizeof(long) - 1) &
> ~(sizeof(long)-1);
>
> (*) This is the line I don't understand.[/color]

Nothing complex about it. The portion "~(sizeof(l ong)-1)" creates
a mask, which will zero a portion of an address so that it is
aligned for longs. That is a '~' complement operator, not a '-'
minus sign. The "+ sizeof(long) - 1" portion advances any address
so that the mask can chop it off, and the result will not be
smaller than the original input address, which is the "(unsigned
long)p" portion. It is all very system specific and non-portable.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Chris Torek]

Re: Interpreting mem_map init code

In article <NPq1e.12377$m3 1.127022@typhoo n.sonic.net>,
zolli <zolli@NoSpamNo How.net> wrote:
[snippage][color=blue]
>(*) start_mem = ((unsigned long)p + sizeof(long) - 1) &
> ~(sizeof(long)-1);
>(*) This is the line I don't understand.
>Using reasonable (?) example values ...[/color]

Chuck Falconer already described the goal, but the action may be
easier to see with additional "reasonable (?)" example values. :-)

Let us assume that sizeof(long) is, numerically speaking, either
4 or 8, since those are in fact typical today. Ignoring all the
funky 0xc0000000 type numbers I snipped, let us take a look at what
happens to values in the range [0..8] if sizeof(long) is 4, and
[0..16] if sizeof(long) is 8.

If sizeof(long)==4 , and assuming p and start are both "unsigned
long", we have:

start = (p + (size_t)4 - 1) & ~((size_t)4 - 1);

which is just:

start = (p + (size_t)3) & ~(size_t)3;

Of course, all we know about size_t -- the type of the result of
sizeof -- is that it is some unsigned integral type, probably either
unsigned int or unsigned long. For simplicitly let us assume it
is also unsigned long:

start = (p + 3UL) & ~3UL;

The ~3UL presumably produces either 0xfffffffc or 0xfffffffffffff ffc,
depending on sizeof(long) again (because we are also assuming that
CHAR_BIT is 8 and there are no "holes" in the value bits of an
unsigned long). As it happens, as long as we stick with numerically
small values, it does not really matter. (But note that if we have
sizeof(long)==8 and sizeof(size_t)= =4, this expression goes awry
for larger values -- this is a small flaw in the code you are
looking at: it uses both "unsigned long" and "size_t", assuming
they are equally correct, when it is possible that only one, or
even none, are the correct integer type for this kind of sneaky
pointer manipulation.)

Anyway, so, now we get a table of values for sizeof(long)==4 :

p p+3 (p+3)&~3
- --- --------
0 3 0

1 4 4
2 5 4
3 6 4
4 7 4

5 8 8
6 9 8
7 10 8
8 11 8

The vertical white space shows how the results group. Note that the
next input (9) jumps to the next output (12).

The table for (p+7)&~7 is left as an exercise. :-)

As another exercise, try computing (p + 7U) & ~7U when p (an unsigned
long) is 0x0123456789abc def, and sizeof(long)==8 ; but sizeof(size_t)= =4,
so that ~7U is actually 0x00000000fffff ff8, instead of the (presumably
desired) 0xfffffffffffff ff8.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[zolli]

Re: Interpreting mem_map init code

Chris Torek wrote:[color=blue]
> In article <NPq1e.12377$m3 1.127022@typhoo n.sonic.net>,
> zolli <zolli@NoSpamNo How.net> wrote:
> [snippage]
>[color=green]
>>(*) start_mem = ((unsigned long)p + sizeof(long) - 1) &
>> ~(sizeof(long)-1);
>>(*) This is the line I don't understand.
>>Using reasonable (?) example values ...[/color]
>
>
> Chuck Falconer already described the goal, but the action may be
> easier to see with additional "reasonable (?)" example values. :-)
>
> Let us assume that sizeof(long) is, numerically speaking, either
> 4 or 8, since those are in fact typical today. Ignoring all the
> funky 0xc0000000 type numbers I snipped, let us take a look at what
> happens to values in the range [0..8] if sizeof(long) is 4, and
> [0..16] if sizeof(long) is 8.
>
> If sizeof(long)==4 , and assuming p and start are both "unsigned
> long", we have:
>
> start = (p + (size_t)4 - 1) & ~((size_t)4 - 1);
>
> which is just:
>
> start = (p + (size_t)3) & ~(size_t)3;[/color]

This simplification makes things much easier to understand.
[color=blue]
> Of course, all we know about size_t -- the type of the result of
> sizeof -- is that it is some unsigned integral type, probably either
> unsigned int or unsigned long. For simplicitly let us assume it
> is also unsigned long:
>
> start = (p + 3UL) & ~3UL;
>
> The ~3UL presumably produces either 0xfffffffc or 0xfffffffffffff ffc,
> depending on sizeof(long) again (because we are also assuming that
> CHAR_BIT is 8 and there are no "holes" in the value bits of an
> unsigned long). As it happens, as long as we stick with numerically
> small values, it does not really matter. (But note that if we have
> sizeof(long)==8 and sizeof(size_t)= =4, this expression goes awry[/color]

I tried this, and you're right: the results are unexpected.
[color=blue]
> for larger values -- this is a small flaw in the code you are
> looking at: it uses both "unsigned long" and "size_t", assuming
> they are equally correct, when it is possible that only one, or
> even none, are the correct integer type for this kind of sneaky
> pointer manipulation.)
>
> Anyway, so, now we get a table of values for sizeof(long)==4 :
>
> p p+3 (p+3)&~3
> - --- --------
> 0 3 0
>
> 1 4 4
> 2 5 4
> 3 6 4
> 4 7 4
>
> 5 8 8
> 6 9 8
> 7 10 8
> 8 11 8[/color]

Ahh. The light just came on!
[color=blue]
> The vertical white space shows how the results group. Note that the
> next input (9) jumps to the next output (12).
>
> The table for (p+7)&~7 is left as an exercise. :-)
>
> As another exercise, try computing (p + 7U) & ~7U when p (an unsigned
> long) is 0x0123456789abc def, and sizeof(long)==8 ; but sizeof(size_t)= =4,
> so that ~7U is actually 0x00000000fffff ff8, instead of the (presumably
> desired) 0xfffffffffffff ff8.[/color]

Have you ever been a teacher? Thanks for the patient explanations.

Cheers,
zolli

[CBFalconer]

Re: Interpreting mem_map init code

zolli wrote:[color=blue]
> Chris Torek wrote:
>[/color]
.... snip ...[color=blue][color=green]
>>
>> Anyway, so, now we get a table of values for sizeof(long)==4 :
>>
>> p p+3 (p+3)&~3
>> - --- --------
>> 0 3 0
>>
>> 1 4 4
>> 2 5 4
>> 3 6 4
>> 4 7 4
>>
>> 5 8 8
>> 6 9 8
>> 7 10 8
>> 8 11 8[/color]
>
> Ahh. The light just came on!
>[color=green]
>> The vertical white space shows how the results group. Note that
>> the next input (9) jumps to the next output (12).
>>
>> The table for (p+7)&~7 is left as an exercise. :-)
>>
>> As another exercise, try computing (p + 7U) & ~7U when p (an
>> unsigned long) is 0x0123456789abc def, and sizeof(long)==8 ; but
>> sizeof(size_t)= =4, so that ~7U is actually 0x00000000fffff ff8,
>> instead of the (presumably desired) 0xfffffffffffff ff8.[/color]
>
> Have you ever been a teacher? Thanks for the patient explanations.[/color]

I think he is. Illustrating once again the enormous difference
between simply knowing what you are talking about and being able to
teach it. I would have gone on muttering about masks and never
thought of a table.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson