User implementable standard library functions

[Francine.Neary]

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }


Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

 

[Flash Gordon]

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }


Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

free, fopen, fclose (you can implement getc using fgetc or the other war
around ;-)), signal, remove, rename, abort, offsetof (OK, so it's a
macro) to name just a few. I'm assuming ignoring implementations that
always fail just as you did.

 

[pete]

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }


Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

I don't know, but I have a toy C library here:

http://www.mindspring.com/~pfilandr/C/library/

 

[santosh]

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }


Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise, the
is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system, the va_* macros,
time functions.

 

[pete]

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite,
fgetc, exit, signal, raise, the
is* character test functions,

isdigit can be implemented.
It is not locale dependent.

 

[Richard Heathfield]

pete said:

isdigit can be implemented.
It is not locale dependent.

The same applies to isxdigit, and (without looking it up) probably
isspace - and perhaps one or two others in the same vein.

I suspect that strftime can be implemented portably.

 

[cr88192]

One interesting thing to come out of the recent "Alignment" thread is
that it is impossible to write a portable replacement for malloc in
"user space" (not sure what the right term is - I mean an ordinary
programmer, not an implementor) - even a naive method using a large
array isn't guaranteed to work if there's no way of having a variable
of strictest alignment. Oh, for the sake of the pedants, let's
discount
void *my_malloc(size_t size) { return 0; }

well, yes we can, if we grab the original memory from malloc that is...
of course, then for example, I detect linux, and go over to using mmap
instead (for some things, this is needed...).

this is often what I do in my allocators at least...

this often works well for specialized allocators and for garbage collectors.


likewise for wrapping other functionality (such as stdio and posix calls) in
the name of yet more features (a VFS system and being able to mount zipfiles
as part of the directory tree...).

maybe not the same, oh well...

Of course, for most standard library functions, say something like
strlen, it's perfectly possible to provide a completely equivalent
implementation yourself.

So as an academic exercise, which other standard library functions
share the same property as malloc, that the ordinary programmer is
powerless to write an equivalent function without dipping into non-
Standard implementation details?

there are lots.

of course, I am not exactly staying in standards land either for that
matter...

I have my own runtime C compiler hack-job linking against statically
compiled parts of the app, and then I go off and implement some blatently
non-standard compiler extensions (geometric vectors and quaternions as
built-in types, among other things...).

works, does what I want, if albeit one has to choose their targets carefully
(currently working on mingw and windows on x86, and, errm...). well, apart
from a few things (not completed yet), my compiler-core should be almost
workable on linux x86-64...

ok, x86 windows is my main target...

 

[Kenneth Brody]

well, yes we can, if we grab the original memory from malloc that is...
of course, then for example, I detect linux, and go over to using mmap
instead (for some things, this is needed...).

How do you portably guarantee proper alignment?

[...]

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>

 

[Francine.Neary]

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise, the
is* character test functions, perror, sterror, locale functions,

You mean strerror.

 

[Harald van =?UTF-8?B?RMSzaw==?=]

From the top of my head:

free, fopen, fclose, freopen, fread, fwrite, fgetc, exit, signal, raise,
the is* character test functions, perror, sterror, locale functions,
setjmp/longjmp, fflush, remove, tmpfile, abort, system, the va_* macros,
time functions.

fread/fwrite can be implemented portably by calling to fgetc/fputc, or
fgetc/fputc can be implemented portably by calling fread/fwrite; whichever
you choose, you can cross one pair off of your list. (You included fgetc
but not fputc; I'm assuming that was an oversight.)

In addition to the functions you listed, most of the floating point math
functions are notable in that they can be implemented portably, but cannot
be implemented portably in a way that's likely to actually be useful.

 

[CBFalconer]

cr88192 wrote:
.... snip ...

How do you portably guarantee proper alignment?

You don't. You can't. You use malloc or declare variables..

 

[pete]

fread/fwrite can be implemented portably by calling to fgetc/fputc, or
fgetc/fputc can be implemented portably by calling fread/fwrite;

fgetc and fputc are much easier to implement than that:

#include <stdio.h>

int fputc(int c, FILE *stream)
{
return putc(c, stream);
}

int fgetc(FILE *stream)
{
return getc(stream);
}

 

[cr88192]

How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment is (on
x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.


now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

for other cases, it should be mostly tweaking...

 

[Keith Thompson]

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

now, aligning memory, well this depends on the type sizes, ...

a general option is this (should work on windows-32 bit, linux, and linux
x86-64, and maybe a few others):
p=(void *)((((long)p)+15)&(~15)); //aligns to a 16 byte boundary

No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.

 

[cr88192]

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.

ifdef powers, ifdef fixes everything...


hell, even chunks of inline assember and w32api calls can be made 'portable'
using ifdef (if by portable, one means, not included except on their
specific targets...).

likewise, going and opening the EXE and ripping out the symbol table is not
portable either, but can be done in portable projects via the powers of
ifdef...

No, this is not guaranteed to work. The result of converting of a
pointer to an integer or vice versa is implementation-defined. It's
also not guaranteed that 'long' is wide enough to hold a pointer
value. Even if it is, the result could easily be negative; using
'unsigned long' would avoid that problem, but not the others.

I didn't say it was gueranteed to work, or even all that portable, only that
it works on x86 and friends in the compilers most people are likely to use
(gcc and msvc...).

also note that on x86-64, pointers are signed, so 'long' (or 'long long', if
win-x64 is a possibility) is a good option.

my case:
I usually detect, using 'int' on x86 and 'long long' on x86-64.

 

[CBFalconer]

[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's
alignment is (on x86 and friends, usually at least 8 or 16 I
think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.

But not good enough for c.l.c, which discusses the C language, as
defined by the C standard and historical standards. If you want to
discuss mmap, post its complete code, written in purely standard
C. Otherwise it is off-topic.

 

[Keith Thompson]

news:[email protected]... [...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.

That's irrelevant here in comp.lang.c.

ifdef powers, ifdef fixes everything...

Hardly. If mmap isn't supported, you still have to find some
alternative.

[...]

I didn't say it was gueranteed to work, or even all that portable, only that
it works on x86 and friends in the compilers most people are likely to use
(gcc and msvc...).

Again, that's not particularly relevant here.

also note that on x86-64, pointers are signed, so 'long' (or 'long long', if
win-x64 is a possibility) is a good option.

It depends on what you want to do with the converted result. I don't
use bitwise operators on signed integers, and I don't remember what
(blah+15)&(~15) does if blah is signed and has a negative value.

my case:
I usually detect, using 'int' on x86 and 'long long' on x86-64.

If you have <stdint.h>, you can use intptr_t or uintptr_t (if they
exists). If you don't, I'll mention that I've never used a system on
which different pointer types have different sizes, or on which
sizeof(void*) ! sizeof(long). Neither assumption is guaranteed, of
course, and I have no doubt that systems exist that violate them.

 

[cr88192]

[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment
is (on x86 and friends, usually at least 8 or 16 I think...).

and, if from mmap, it is aligned to a page boundary.

mmap is not portable.

it exists on linux...
good enough for if running on linux, just have to detect and use.

That's irrelevant here in comp.lang.c.

but is relevant for actual coding, where most non-trivial code ends up
having to deal with the underlying implementation in one non-standard way or
another...

unless you mean to say: c.l.c is only for theory, not for actual practice...

Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.

on linux, mmap offers some powers over malloc:
page-aligned memory;
less overhead;
PROT_EXEC (because, on linux x86-64, stuff segfaults if one tries to run
code in buffers allocated with malloc);
forcing stuff into the low 2GB (my runtime text and data/bss sections);
....

so, which is used is controlled by a few ifdefs.

[...]

I didn't say it was gueranteed to work, or even all that portable, only
that
it works on x86 and friends in the compilers most people are likely to
use
(gcc and msvc...).

Again, that's not particularly relevant here.

also note that on x86-64, pointers are signed, so 'long' (or 'long long',
if
win-x64 is a possibility) is a good option.

It depends on what you want to do with the converted result. I don't
use bitwise operators on signed integers, and I don't remember what
(blah+15)&(~15) does if blah is signed and has a negative value.

one need only think in binary...
in this case, it rounds up to the next 16 boundary, headed towards 0.

of course, it does assume 2's complement, but I will argue this is near
universal...

I suppose one can avoid 2's complement dependency by using plain arithmetic
instead:
'((i+15)/16)*16'.

If you have <stdint.h>, you can use intptr_t or uintptr_t (if they
exists). If you don't, I'll mention that I've never used a system on
which different pointer types have different sizes, or on which
sizeof(void*) ! sizeof(long). Neither assumption is guaranteed, of
course, and I have no doubt that systems exist that violate them.

yes, windows x64.

sizeof(void *)==8
sizeof(long)==4

'stdint', hadn't thought of using it in this case...

 

[Richard Tobin]

it exists on linux...
good enough for if running on linux, just have to detect and use.

[/QUOTE]

That's irrelevant here in comp.lang.c.

And more to the point, irrelevant to this thread. We're not discussing
a practical problem here, just an interesting exercise: seeing just
how much of the standard library can be defined in terms of standard C.

-- Richard

 

[Kenneth Brody]

[...]
How do you portably guarantee proper alignment?

if grabbed from malloc, it is aligned to whatever malloc's alignment [...]
ifdef powers, ifdef fixes everything...

Hardly. If mmap isn't supported, you still have to find some
alternative.

on windows, I use malloc.

[...]

But wasn't the original question along the lines of "how can one
write a replacement for (not a wrapper around) malloc()"?

(Okay, it was actaully more along the lines of "which standard
library functions could be implemented by an end user, rather
than the implementor".)

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>