Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Internal implementation of realloc

Reply
Thread Tools

Internal implementation of realloc

 
 
Chris Torek
Guest
Posts: n/a
 
      09-05-2008
>On Sep 4, 3:22*pm, "Malcolm McLean" <(E-Mail Removed)> wrote:
>>... if memory is paged it might be possible to [implement realloc()
>>via] remap[ping] the page addresses without physically copying data.


In article <(E-Mail Removed)>,
Gene <(E-Mail Removed)> wrote:
>This occurred to me, too.
>
>If you think about it, though, it won't work unless malloc()
>cooperates.


Well, certainly; but malloc() and realloc() must always cooperate.
(This is one of the pitfalls of attempting to substitute in a
different malloc(). Even if you handle malloc()+free()+realloc(),
you may not realize that you also had to gimmick the __vmalloc()
and __pagealloc() functions, which are attempting to cooperate with
malloc() and which are called directly from, e.g., the stdio
routines, for I/O-via-page-swapping.)

>The expansion takes place in _virtual memory space_ not
>physical. I.e. if malloc() hands out blocks that are contiguous in
>virtual space, remapping won't help because when you try to grow a
>block, malloc() has probably already given up the virtual addresses
>immediately above.


This is not a problem, because the caller must write:

original_region = malloc(original_size); /* called O and S below */
... do appropriate work with it ...
new_region = realloc(original, new_size); /* called N and T below */

The realloc() call can obtain any available (and suitable, if there
are restrictions) set of virtual addresses, then ask the OS to move
the physical pages from the old address-space -- the region underlying
the virtual address range in [O..O+S-1] -- to the new range [N..N+T-1]
(with "new" pages added at the end if needed, or "old" pages removed
if T < S; and of course S and T are page-rounded and O and N must be
page-aligned).

If the pages are *moved* (as opposed to simply multiply-mapped),
this also gives you a Feature: subsequent access to original_region[i]
will fail ("segfault" or "bus error" or whatever), which will help
the programmer find any "stale" pointers. This technique is quite
useful for debugging, and hence doing page-moving into "fresh"
virtual space on *every* memory allocation -- even those that can
be done without such a move -- can be valuable. Similarly, one
can unmap the page(s) backing any region that has been free()d.

(I used this trick to find a bug in the 4.3BSD kernel once.)

>Now 64-bit addresses open a new possibility. If every malloc (at
>least up up to 4 billion of them) returns an address with the lower
>(say) 32-bits zero, then every block can be grown to 4gb by remapping
>pages.


If you parcel out virtual addresses on 4GB boundaries, you can
expand in-place even *without* page-remapping. (Well, assuming
the physical page size is less than 4GB, at least. )
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      09-05-2008
Chris Torek wrote:
> Gene <(E-Mail Removed)> wrote:
>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>
>>> ... if memory is paged it might be possible to [implement realloc()
>>> via] remap[ping] the page addresses without physically copying data.

>>
>> This occurred to me, too. If you think about it, though, it
>> won't work unless malloc() cooperates.

>
> Well, certainly; but malloc() and realloc() must always cooperate.
> (This is one of the pitfalls of attempting to substitute in a
> different malloc(). Even if you handle malloc()+free()+realloc(),
> you may not realize that you also had to gimmick the __vmalloc()
> and __pagealloc() functions, which are attempting to cooperate with
> malloc() and which are called directly from, e.g., the stdio
> routines, for I/O-via-page-swapping.)


What __vmalloc and __pagealloc functions? No such thing in std C.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      09-05-2008
Eric Sosman wrote:
> CBFalconer wrote:
>> Chris Torek wrote:
>>> Gene <(E-Mail Removed)> wrote:
>>>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>>>
>>>>> ... if memory is paged it might be possible to [implement
>>>>> realloc() via] remap[ping] the page addresses without
>>>>> physically copying data.
>>>>
>>>> This occurred to me, too. If you think about it, though, it
>>>> won't work unless malloc() cooperates.
>>>
>>> Well, certainly; but malloc() and realloc() must always cooperate.
>>> (This is one of the pitfalls of attempting to substitute in a
>>> different malloc(). Even if you handle malloc()+free()+realloc(),
>>> you may not realize that you also had to gimmick the __vmalloc()
>>> and __pagealloc() functions, which are attempting to cooperate with
>>> malloc() and which are called directly from, e.g., the stdio
>>> routines, for I/O-via-page-swapping.)

>>
>> What __vmalloc and __pagealloc functions? No such thing in std C.

>
> Typos: Chris actually meant _vmalloc() and _pagealloc().


I still don't find those names, with or without leading '_', in the
standard.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      09-06-2008
CBFalconer wrote:
> Eric Sosman wrote:
>> CBFalconer wrote:
>>> Chris Torek wrote:
>>>> Gene <(E-Mail Removed)> wrote:
>>>>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>>>>
>>>>>> ... if memory is paged it might be possible to [implement
>>>>>> realloc() via] remap[ping] the page addresses without
>>>>>> physically copying data.
>>>>> This occurred to me, too. If you think about it, though, it
>>>>> won't work unless malloc() cooperates.
>>>> Well, certainly; but malloc() and realloc() must always cooperate.
>>>> (This is one of the pitfalls of attempting to substitute in a
>>>> different malloc(). Even if you handle malloc()+free()+realloc(),
>>>> you may not realize that you also had to gimmick the __vmalloc()
>>>> and __pagealloc() functions, which are attempting to cooperate with
>>>> malloc() and which are called directly from, e.g., the stdio
>>>> routines, for I/O-via-page-swapping.)
>>> What __vmalloc and __pagealloc functions? No such thing in std C.

>> Typos: Chris actually meant _vmalloc() and _pagealloc().

>
> I still don't find those names, with or without leading '_', in the
> standard.
>

Isn't it obvious from the context what they do? It's hard to tell if
you are being dense or obtuse.

--
Ian Collins.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      09-06-2008
CBFalconer <(E-Mail Removed)> writes:
> Eric Sosman wrote:
>> CBFalconer wrote:
>>> Chris Torek wrote:
>>>> Gene <(E-Mail Removed)> wrote:
>>>>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>>>>
>>>>>> ... if memory is paged it might be possible to [implement
>>>>>> realloc() via] remap[ping] the page addresses without
>>>>>> physically copying data.
>>>>>
>>>>> This occurred to me, too. If you think about it, though, it
>>>>> won't work unless malloc() cooperates.
>>>>
>>>> Well, certainly; but malloc() and realloc() must always cooperate.
>>>> (This is one of the pitfalls of attempting to substitute in a
>>>> different malloc(). Even if you handle malloc()+free()+realloc(),
>>>> you may not realize that you also had to gimmick the __vmalloc()
>>>> and __pagealloc() functions, which are attempting to cooperate with
>>>> malloc() and which are called directly from, e.g., the stdio
>>>> routines, for I/O-via-page-swapping.)
>>>
>>> What __vmalloc and __pagealloc functions? No such thing in std C.

>>
>> Typos: Chris actually meant _vmalloc() and _pagealloc().

>
> I still don't find those names, with or without leading '_', in the
> standard.


I'm 99.99% certain that Chris Torek is aware of that -- and that's
probably an underestimate.

Replacing one or more of the standard library functions causes
undefined behavior. Chris was illustrating one way in which that
undefined behavior can manifest itself as things going badly wrong
rather than as things working as one might naively expect. Think of
_vmalloc() and _pagealloc() as *examples* of things within the
internals of a standard library implementation that can cause problems
when you start mucking around with replacements for standard library
functions.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      09-06-2008
Keith Thompson wrote:
> CBFalconer <(E-Mail Removed)> writes:
>> Eric Sosman wrote:
>>> CBFalconer wrote:
>>>> Chris Torek wrote:
>>>>> Gene <(E-Mail Removed)> wrote:
>>>>>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>>>>>
>>>>>>> ... if memory is paged it might be possible to [implement
>>>>>>> realloc() via] remap[ping] the page addresses without
>>>>>>> physically copying data.
>>>>>>
>>>>>> This occurred to me, too. If you think about it, though, it
>>>>>> won't work unless malloc() cooperates.
>>>>>
>>>>> Well, certainly; but malloc() and realloc() must always cooperate.
>>>>> (This is one of the pitfalls of attempting to substitute in a
>>>>> different malloc(). Even if you handle malloc()+free()+realloc(),
>>>>> you may not realize that you also had to gimmick the __vmalloc()
>>>>> and __pagealloc() functions, which are attempting to cooperate with
>>>>> malloc() and which are called directly from, e.g., the stdio
>>>>> routines, for I/O-via-page-swapping.)
>>>>
>>>> What __vmalloc and __pagealloc functions? No such thing in std C.
>>>
>>> Typos: Chris actually meant _vmalloc() and _pagealloc().

>>
>> I still don't find those names, with or without leading '_', in the
>> standard.

>
> I'm 99.99% certain that Chris Torek is aware of that -- and that's
> probably an underestimate.
>
> Replacing one or more of the standard library functions causes
> undefined behavior. Chris was illustrating one way in which that
> undefined behavior can manifest itself as things going badly wrong
> rather than as things working as one might naively expect. Think of
> _vmalloc() and _pagealloc() as *examples* of things within the
> internals of a standard library implementation that can cause problems
> when you start mucking around with replacements for standard library
> functions.


If you qualify it like that, fine. There are simpler illustrations
of the dangers of replacing malloc. For example, it may be used in
the initialization code, and prelinked there.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
 
Reply With Quote
 
Richard
Guest
Posts: n/a
 
      09-06-2008
Ian Collins <(E-Mail Removed)> writes:

> CBFalconer wrote:
>> Eric Sosman wrote:
>>> CBFalconer wrote:
>>>> Chris Torek wrote:
>>>>> Gene <(E-Mail Removed)> wrote:
>>>>>> "Malcolm McLean" <(E-Mail Removed)> wrote:
>>>>>>
>>>>>>> ... if memory is paged it might be possible to [implement
>>>>>>> realloc() via] remap[ping] the page addresses without
>>>>>>> physically copying data.
>>>>>> This occurred to me, too. If you think about it, though, it
>>>>>> won't work unless malloc() cooperates.
>>>>> Well, certainly; but malloc() and realloc() must always cooperate.
>>>>> (This is one of the pitfalls of attempting to substitute in a
>>>>> different malloc(). Even if you handle malloc()+free()+realloc(),
>>>>> you may not realize that you also had to gimmick the __vmalloc()
>>>>> and __pagealloc() functions, which are attempting to cooperate with
>>>>> malloc() and which are called directly from, e.g., the stdio
>>>>> routines, for I/O-via-page-swapping.)
>>>> What __vmalloc and __pagealloc functions? No such thing in std C.
>>> Typos: Chris actually meant _vmalloc() and _pagealloc().

>>
>> I still don't find those names, with or without leading '_', in the
>> standard.
>>

> Isn't it obvious from the context what they do? It's hard to tell if
> you are being dense or obtuse.


Both. It's called being "chuckish".

 
Reply With Quote
 
Kenny McCormack
Guest
Posts: n/a
 
      09-06-2008
In article <g9u4m4$jt9$(E-Mail Removed)>,
Richard <(E-Mail Removed)> wrote:
....
>> Isn't it obvious from the context what they do? It's hard to tell if
>> you are being dense or obtuse.

>
>Both. It's called being "chuckish".


By the way, who is older: CBF or John McCain?

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
837. Unable to see internal web server from internal server. eric the brave Cisco 0 03-05-2006 01:52 PM
Cisco PIX 501 - Port forwarded to an internal host via Static NAT doesn't work from internal host JoelSeph Cisco 9 01-23-2006 03:52 PM
Internal Client Accessing Internal Server Via Public IP Address GeekMarine1972 Cisco 1 01-15-2005 02:49 AM
Redirect Internal IP to Different Internal IP on Same Subnet & Interface EG Cisco 5 12-30-2004 02:10 AM
internal to internal NAT? Mike Cisco 1 04-21-2004 12:15 PM



Advertisments