Hi,

Ricardo B (ricardo.b.delete@this.xxxxx.xx) on January 12, 2020 11:04 am wrote:
> Adrian (a.delete@this.acm.org) on January 11, 2020 11:18 pm wrote:
> > Ricardo B (ricardo.b.delete@this.xxxxx.xx) on January 11, 2020 7:01 pm wrote:
> > >
> > > Your belief is difficult to prove because it's paradoxically impossible
> > > You cannot avoid physical memory fragmentation without a translation layer somewhere.
> > > And having it the CPU handle it is the fastest known method.
> > >
> > > You're also vastly underestimating the use cases of memory paging.
> > > There's memory mapped files, copy-on-write sharing, running 32-bit apps on
> > > 64-bit systems, and probably some other features I'm forgetting right now.
> >
> > It is not paradoxically impossible. There are various methods to avoid physical memory fragmentation.
> >
> > The worst method, but which is guaranteed to always succeed, is to move some memory from time to time.
>
> This requires the ability to pause the software, identify all pointers to a chunk
> of memory and re-write all of these pointers after moving the chunk of memory.
>
> This has been the subject of much research and exploited in languages
> with managed memory allocation and garbage collection (e.g. Java)
>
> a) There's a performance hit.
> b) It only works for such languages. Languages like C/C++ give too much freedom.

Typically when segmentation is being used, a "pointer" is either an offset in a segment or a "segment_number:offset" pair; and you can move a segment's data, then change the base address of the segment. All of the pointers still contain the correct "offset in segment" (and correct "segment_number") afterwards and do not need to be found/modified at all.

Often (e.g. for 32-bit 80x86) it's also not always necessary to pause the software. Specifically; you can set the segment to "read only" and reload the segment register/s, then copy it (without altering the original - source and dest can't overlap), then update the segment base and change the segment back to "read/write", then reload the segment register/s again. If the software tries to modify the data while you're copying it then it will get a general protection fault and the general protection fault handler can do "pause this thread only, until segment move completed" so that the pause only happens when absolutely necessary.

Of course for performance (and maybe other reasons) you'd really want multiple smaller segments (rather than having all of a program's data in a single huge segment) so that you're moving smaller amounts of data and so that there's less chance of a write causing a pause, which means that you want pointers to be "segment_number:offset". However; on (32-bit) 80x86, segment register loads are slow, so you end up having to choose between worse performance (for defragging physical memory) and worse performance (due to segment register loads).

Also note that modern 80x86 CPUs cheat - when segment bases are zero they skip the "address = segment_base + offset" addition (and just use "offset" as the address instead); and having non-zero segment bases will cause extra overhead for every memory access. Because of this (and because of TLB misses, and because of the performance differences in modifying segment's details which would become iteration over page tables and TLB flushes instead of atomic writes to GDT/LDT descriptors, and because of the performance difference between segment register loads and not having segment register loads) the performance differences of "segmentation vs. paging" can't be accurately estimated without true segmentation (e.g. by using paging to emulate segmentation, as I believe Adrian is planning to do) and you'd have to use (32-bit) 80x86 (which is the only CPU I can think of that still provides true segmentation).

> > The conventional wisdom is that all alternatives to dynamic
> > address translation via paging have lower performance.
> >
> > This may be true, but I have seen no proof that this has remained true on modern
> > hardware, compared to the 1977 hardware when this dogma became established.
> >
> > That is why I intend to discover experimentally whether this is true or false. However
> > it is likely that I will not know the answer before the end of the year, because besides
> > this there are many other experimental features that I want to implement in a custom
> > kernel variant, and this being a hobby project, it will progress slowly.
> >
> > All the other things mentioned by you can also be implemented without dynamic address
> > translation, but it is unknown yet whether this would not worsen the performance.
>
> To state CoW can be implemented without address translation is a rather extraordinary
> claim requiring some rather extraordinary evidence besides handwaving.
>
> All in all I get the distinct feeling you're ignoring decades
> of academic research and actual deployment of alternatives.

You can do "copy entire segment on write", which is awful for the "one single huge segment for all of a program's data" case, but not necessarily awful for the "many separate smaller segments" case.

The other thing that might be worth researching is "spectre-like" vulnerabilities (if information can be leaked from segments an attacker shouldn't have access to, and/or if using segmentation prevents information from leaking).

- Brendan