Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Visual overview of a custom malloc() implementation

silent-tower.net

Post reply on HN
Print view View original

21–30 of 31 posts

Re: Visual overview of a custom malloc() implementation

#21

Post by mort96 »

anonymousDan wrote: post #11

Is segmentation still viewed as terrible? There seems to be a trend towards hardware mechanisms for more fine-grained intra-process memory protection than is practical with paging. Nice intro though.

Segmentation is a horrible hack to make it possible to have a larger address space than what the word size of the machine would otherwise suggest.

Partitioning the address space into regions with more fine-grained permission controls than what traditional MMUs do is fine and all, but it's orthogonal to segmented memory. Having large enough machine words to not have to think about near pointers and far pointers is great.

Re: Visual overview of a custom malloc() implementation

#22

Post by flohofwoe »

acuozzo wrote: post #17
astrange wrote: post #5

Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.

Do you know if any of the popular static analysis tools detect mistakes like this?

Clang has a -Wreserved-identifier warning, but that's only for reserved identifiers in the C standard, not for POSIX (e.g. names starting with double underscore or a single underscore followed by a capital letter).

The C standard has many more such adhoc reserved identifiers, for instance anything starting with `is`, `str` or `wcs` followed by a lowercase letter is technically a reserved identifier, hell, even any preprocessor macro starting with an `E` followed by a digit or uppercase letter is reserved.

Theoretically those reserved identifiers in the C standard matter more than _t because they affect all C code, not just C code targeting POSIX, yet nobody ever brings those up (because these are really only theoretical problems, and should they turn into actual problems one day they are trivial to fix).

It's important to differentiate between the C standard (e.g. what C compilers care about) and the POSIX standard (which C compilers do not care about), since not all C code runs on POSIX systems. It's only on some UNIXes where those two worlds overlap.

In the real-world, using _t typenames really is a complete non-issue.

Re: Visual overview of a custom malloc() implementation

#23

Post by matheusmoreira »

astrange wrote: post #5

Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.

POSIX is just a bunch of rules some committee made up. People aren't obligated to abide by them. They should get rid of their "reservation" rule, it's pointless since people learn by copying examples and there's tons of _t type examples out there. It's not like the POSIX police will arrest them for it.

Re: Visual overview of a custom malloc() implementation

#24

Post by cozzyd »

astrange wrote: post #5

Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.

Essentially everyone does this though...

Ask long as your prefix your types it's unlikely to be a problem

Re: Visual overview of a custom malloc() implementation

#25

Post by matheusmoreira »

masklinn wrote: post #6
astrange wrote: post #5

Unfortunately the author is violating POSIX here by defining his own _t types, which is a suffix reserved for the system. Too bad since everyone likes it.

Also unfortunate are the use of a heap segment representation, and sbrk.

I understand why the use of sbrk is unfortunate but what's wrong with the representation? Are there better ones?

Re: Visual overview of a custom malloc() implementation

#27

Post by mort96 »

flohofwoe wrote: post #13
anonymousDan wrote: post #11

Is segmentation still viewed as terrible? There seems to be a trend towards hardware mechanisms for more fine-grained intra-process memory protection than is practical with paging. Nice intro though.

I'm not an expert in memory allocation strategies, but AFAIK fragmentation can still be a problem with a naive allocator that doesn't group small allocations (less than a page size) into buckets. You won't run out of virtual address space (as was the case with 32-bit processes on computers with much more than 4 GB physical memory), but you may run out of physical memory if the allocator is "blocking" a whole memory p…

Segmentation isn't fragmentation. "Segmentation" is when you have a machine with 16 bit machine words, which would usually mean you can only address up to 2^16 = 65536 bytes of memory, but you want to support up to 1 MiB of RAM so you add a segment register and read all memory reads as relative to (segment register This results in a split between "near pointers" and "far pointers". "Near pointers" are pointers which are 16 bit and assumed to be relative to the "current segment", and can thus be dereferenced directly with any memory load instruction. "Far pointers" are 32 bit and carry a segment part and a relative part, and to dereference it, you must first write the segment part to the segment register, then do the memory load instruction with the relative part, and then you probably wanna clean up after yourself by restoring the segment register to its old state.

There were multiple segment registers too, one used for data ("heap") memory operations, one for stack memory operations, one for reading machine code, and some extra segments for convenience. You had to remember which of the segment registers your near pointer was supposed to be relative to.

If this all sounds very tedious... well, it was, and that's why, yes, segmentation is still viewed as terrible :)

(I wasn't around back when this was common, but I did write some 16-bit real mode code for a bootloader for an OS course once, and I have designed and implemented some toy 8 bit CPUs which used segmentation to have more than 256 bytes of RAM, so I do have some experience with it)

Re: Visual overview of a custom malloc() implementation

#28

Post by masklinn »

matheusmoreira wrote: post #25
masklinn wrote: post #6

Earlier quoted context omitted.

Also unfortunate are the use of a heap segment representation, and sbrk.

I understand why the use of sbrk is unfortunate but what's wrong with the representation? Are there better ones?

The heap growing towards the stack is a property of the heap segment (used by brk/sbrk). mmap is not bound to this model, and unless used with MAP_FIXED can associate the allocation with virtual addresses anywhere in the address space.

Re: Visual overview of a custom malloc() implementation

#29

Post by hgs3 »

tlb wrote: post #26
tilt_error wrote: post #3

Why are the letters ’p’, ’q’ and ’t’ missing from the article? Makes it a bit annoying to read.

No 'r's or '3's on Safari/Mac. It's a custom font 'Cantarell', evidently a bit broken.

> evidently a bit broken

And here I thought the author was making a fragmentation joke.

Re: Visual overview of a custom malloc() implementation

#30

Post by flohofwoe »

mort96 wrote: post #27
flohofwoe wrote: post #13

Earlier quoted context omitted.

I'm not an expert in memory allocation strategies, but AFAIK fragmentation can still be a problem with a naive allocator that doesn't group small allocations (less than a page size) into buckets. You won't run out of virtual address space (as was the case with 32-bit processes on computers with much more than 4 GB physical memory), but you may run out of physical memory if the allocator is "blocking" a whole memory p…

Segmentation isn't fragmentation. "Segmentation" is when you have a machine with 16 bit machine words, which would usually mean you can only address up to 2^16 = 65536 bytes of memory, but you want to support up to 1 MiB of RAM so you add a segment register and read all memory reads as relative to (segment register This results in a split between "near pointers" and "far pointers". "Near pointers" are pointers which…

Ah right, I totally misread segmentation as fragmentation, sorry.

IMHO a more flexible segmentation system (exposed as base-pointer plus offset) wouldn't actually be bad if properly supported by high level languages. You could treat the base pointer as 'private knowledge' inside a system and only hand out the offset as a 'public handle'. To access a specific address you need both the private base pointer and public offset handle, and the base pointer could also move around without invalidating the offset handles in the wild.

Of course all this can be done purely in software too already.

Post reply on HN