OSDev.org

Hi,

Segmentation has 2 different purposes: memory management, and protection.

For virtual memory management, segmentation sucks badly. Unlike paging, it does not solve fragmentation problems. Unlike paging, you can't arbitrarily map small piece/s to something else (e.g. swap space, memory mapped files, etc). For these reasons segmentation is useless for virtual memory management (unless you also use paging). If you use paging and segmentation; then (for virtual memory management purposes) segmentation becomes a redundant waste of time.

For protection; there's an unavoidable compromise between granularity and overhead - the more checking you do the more it costs. If you know that software is correct, then protection checks are pointless and you want maximum performance with no useless protection checks. Sadly, for most software we can only assume it's correct (until/unless there's proof that it's not). In this case we want a small amount of protection (with a small amount of overhead) just in case (e.g. some isolation between processes, rather than fine-grained "object level" protection). If we're using paging for virtual memory management anyway, then paging can easily provide "a small amount of protection just in case" with very little additional overhead.

If you don't know if software is correct (you're debugging, doing unit tests, etc) then you want very fine granularity protection and don't care much about the overhead/performance. In this case, you want something more powerful than segmentation, that's capable of detecting a much larger variety of problems. For example, if something sets a variable to an out of range value ("int celcius = -1000;") then it's a bug that segmentation won't detect, if some data is protected by a mutex and someone modifies it without acquiring the mutex then that's a bug that segmentation won't detect, if someone gets a raw input string from the user and displays it on a web page then that's a bug that segmentation won't detect, if someone writes floating point values to an array of integers then that's a bug that segmentation won't detect, etc. If you want adequate debugging/testing tools that are capable of detecting a wide variety of bugs, then segmentation isn't adequate for this purpose. Instead you want something like a virtual machine that operates on the level of the language's abstract machine (and does things like run-time type checking, range checking, etc), or maybe something like a managed language.

Basically; for all possible purposes, segmentation is inferior to alternatives.


Cheers,

Brendan

Brendan wrote:For virtual memory management, segmentation sucks badly. Unlike paging, it does not solve fragmentation problems. Unlike paging, you can't arbitrarily map small piece/s to something else (e.g. swap space, memory mapped files, etc). For these reasons segmentation is useless for virtual memory management (unless you also use paging). If you use paging and segmentation; then (for virtual memory management purposes) segmentation becomes a redundant waste of time.

Paging doesn't solve virtual memory fragmentation either, you are still left with the fragmentation. Just like in the paging case, a segment can be anywhere in the memory and can be moved. Modern languages with GC also often employ some kind memory compaction. With segmentation you can easily do this by moving the segment to another place in physical memory and just updating the segment descriptor. So in practice you do something that many programs are already doing.

Hi,

OSwhatever wrote:

Brendan wrote:For virtual memory management, segmentation sucks badly. Unlike paging, it does not solve fragmentation problems. Unlike paging, you can't arbitrarily map small piece/s to something else (e.g. swap space, memory mapped files, etc). For these reasons segmentation is useless for virtual memory management (unless you also use paging). If you use paging and segmentation; then (for virtual memory management purposes) segmentation becomes a redundant waste of time.

Paging doesn't solve virtual memory fragmentation either, you are still left with the fragmentation. Just like in the paging case, a segment can be anywhere in the memory and can be moved. Modern languages with GC also often employ some kind memory compaction. With segmentation you can easily do this by moving the segment to another place in physical memory and just updating the segment descriptor. So in practice you do something that many programs are already doing.

Paging solves physical memory fragmentation problems. For example, if you've got a 1234 KiB ".text" section then 309 small 4 KiB pieces scattered throughout the physical address space is fine, and you don't need a single 1234 KiB piece of physically contiguous RAM. This also means that any of those 4 KiB pieces can be in swap space, on disk, etc; while for segmentation (without paging) you're screwed and can't have a segment with pieces in the middle "missing" (on disk, etc).

With segmentation you can move entire segments (to mitigate some of the physical address space fragmentation problem caused by segmentation); but moving segments (especially larger segments) requires slow/expensive memory copy operations; and because many processes are using the same fragmented physical address space it's difficult to de-fragment properly without interrupting other processes and causing scalability problems on modern multi-CPU systems.

Segmentation does solve the virtual address space fragmentation issue, but it does that with segment register loads that require protection checks (and therefore require extra overhead and are slow).

With paging, each process is typically given its own large virtual address space. This means that any virtual address space fragmentation problems are "per process", and because the space is relatively large (e.g. 3 GiB of space per process, on a 32-bit system with only 2 GiB of RAM shared by all processes) the virtual address space fragmentation problems mostly don't occur in the first place.

In summary:

• Paging:
  • has a minor/negligible "virtual address space fragmentation" problem
  • has TLB management overhead (TLB misses, etc)
• Segmentation (without paging):
  • has segment management overhead (GDT/LDT management, segment register loads, etc)
  • has a massive "physical address space fragmentation" problem
  • makes it almost impossible to support things like memory mapped files, swap space, allocation on demand, etc
  • has an unsolvable portability issue (most CPUs don't support it)
  • can provide extra protection/checking that is either unnecessary (most software) or inadequate (debugging, unit testing)
  • is not supported by any modern compiler or toolchain
  • is so retarded that no sane OS has ever used it (or, any OS that uses it is not sane by definition )
• Hybrid (segmentation and paging):
  • has TLB management overhead (TLB misses, etc)
  • has segment management overhead (GDT/LDT management, segment register loads, etc)
  • can provide extra protection/checking that is either unnecessary (most software) or inadequate (debugging, unit testing)
  • is not supported by any modern compiler or toolchain

Cheers,

Brendan

The important issue is that paging doesn't solve the fine-graned object protection issue, which segmentation can do. In order to solve that people have invented interpreted / JIT-languages that does solve that issue, but at a much higher cost than segmentation. Thus, as processor speed no longer significantly improves, it once again should be interesting to look at the segmentation technique (in new designs) that could much better solve the issues with C++-like languages that are much faster.

onlyonemac wrote:I use segmentation because it allows me to load an executable into any part of memory and have it execute without any awareness of where it is located. Thus there are no issues with relocation or anything like that.

Furthermore, my memory model works on the principle of segments: every application has a code/data segment, an extra segment and a stack segment. Using segmentation keeps my stack out the way. The kernel also has additional segments for its own use.

Overall I find using segments logical with the way I'm doing it, because segment:offset basically translates into datablock:value_index.

Yes, this is the same idea as RDOS has. In addition to that, RDOS has position independent self-contained device-drivers that typically use one private code and one private data segment. This eliminates the need to link a kernel, and allows for loading device-drivers without fixup. It also keeps the private code and data of the driver truely private.

Hi,

rdos wrote:The important issue is that paging doesn't solve the fine-graned object protection issue, which segmentation can do. In order to solve that people have invented interpreted / JIT-languages that does solve that issue, but at a much higher cost than segmentation. Thus, as processor speed no longer significantly improves, it once again should be interesting to look at the segmentation technique (in new designs) that could much better solve the issues with C++-like languages that are much faster.

You miss the point:

Brendan wrote:For example, if something sets a variable to an out of range value ("int celcius = -1000;") then it's a bug that segmentation won't detect, if some data is protected by a mutex and someone modifies it without acquiring the mutex then that's a bug that segmentation won't detect, if someone gets a raw input string from the user and displays it on a web page then that's a bug that segmentation won't detect, if someone writes floating point values to an array of integers then that's a bug that segmentation won't detect, etc.

Those interpreted/JIT-languages/managed languages are catching all sorts of problems that segmentation won't and can't detect. Either you need "safe" and segmentation is useless; or you need performance and segmentation is useless.

Basically; for every possible purpose, segmentation is useless.


Cheers,

Brendan

Brendan wrote: [*]Hybrid (segmentation and paging):

• has TLB management overhead (TLB misses, etc)
• has segment management overhead (GDT/LDT management, segment register loads, etc)
• can provide extra protection/checking that is either unnecessary (most software) or inadequate (debugging, unit testing)
• is not supported by any modern compiler or toolchain

[/list]


Cheers,

Brendan

One thing I'll add about the x86's hybrid scheme is that it requires segmentation information to be used in an address calculation before a page table lookup can be performed. For a segmentation scheme to be viable performance-wise, it probably needs to be implemented entirely in terms of paging, rather than as offsets and limits on top of the physical address space or a paged address space. In other words, have a segment descriptor point to a page directory for a paged address space, so that a segment functions as a userspace-visible ASID. That way you can jump straight into your page table lookup instead of waiting for an address calculation.

Brendan wrote: You miss the point:

Brendan wrote:For example, if something sets a variable to an out of range value ("int celcius = -1000;") then it's a bug that segmentation won't detect, if some data is protected by a mutex and someone modifies it without acquiring the mutex then that's a bug that segmentation won't detect, if someone gets a raw input string from the user and displays it on a web page then that's a bug that segmentation won't detect, if someone writes floating point values to an array of integers then that's a bug that segmentation won't detect, etc.

Those interpreted/JIT-languages/managed languages are catching all sorts of problems that segmentation won't and can't detect. Either you need "safe" and segmentation is useless; or you need performance and segmentation is useless.

Most code doesn't need to validate ranges, but only needs to check pointers and array indexes. Thus, it is best to have the basic functionality (segmentation) as a fast standard function, and then you can add value checking, for instance by attaching a callback to every write (possibly also read) within a selector. This should not be implemented as an exception, rather more like the conforming code segment idea of x86. IOW, when the descriptor is created, you could also associate read and write access callbacks to the descriptor. These will call your own code that can validate values.

Hi,

rdos wrote:

Brendan wrote:Those interpreted/JIT-languages/managed languages are catching all sorts of problems that segmentation won't and can't detect. Either you need "safe" and segmentation is useless; or you need performance and segmentation is useless.

Most code doesn't need to validate ranges, but only needs to check pointers and array indexes. Thus, it is best to have the basic functionality (segmentation) as a fast standard function, ...

It's not "basic functionality" (about 100% of software in the real world doesn't use segmentation at all). It's not fast (it's slower than a dead turtle tied to a large rock). It's not "standard" (at least, not part of any recent standard that matters).

rdos wrote:...and then you can add value checking, for instance by attaching a callback to every write (possibly also read) within a selector.

Nobody is that stupid. More likely is a (ahead of time and/or JIT) compiler that inserts checks (for both type and range) whenever those checks can't be proven redundant and removed. Ironically, the end result of this is likely to be more capable of detecting errors than segmentation while also being faster than segmentation (because, unlike segmentation, most checks/overhead would be removed). Java VMs are a good example of this.

rdos wrote:This should not be implemented as an exception, rather more like the conforming code segment idea of x86. IOW, when the descriptor is created, you could also associate read and write access callbacks to the descriptor. These will call your own code that can validate values.

I've overestimated your ability for "stupid". Instead of getting rid of hideously expensive segment register loads, you don't just want to keep them, you want to reload CS twice for every read or write???


Cheers,

Brendan

What you fail to understand Brendan is that a sane implementation of segmentation is much faster than a typical implementation of 2-level paging. You've yourself worried about TLB shoot downs, which are directly related to paging inefficiency. You never need this with segmentation only. Because with a good implementation of segmentation, you don't need paging at all. In fact, a sane implementation of segmentation would load a selector at the same speed as a general register if the selector is in the descriptor cache, which it should be in 99% of the cases.

Hi,

rdos wrote:What you fail to understand Brendan is that a sane implementation of segmentation is much faster than a typical implementation of 2-level paging. You've yourself worried about TLB shoot downs, which are directly related to paging inefficiency. You never need this with segmentation only.

Wrong. If code on one CPU causes a segment to be changed (resized, deleted, etc) and any other CPU might be using the same/modified segment, then you have to do "multi-CPU segment shootdown" so that other CPUs aren't using stale segments.

rdos wrote:Because with a good implementation of segmentation, you don't need paging at all. In fact, a sane implementation of segmentation would load a selector at the same speed as a general register if the selector is in the descriptor cache, which it should be in 99% of the cases.

If you're going to fantasize about stuff that will never exist, then you should be more creative and (at a minimum) include a talking piece of cheese and maybe a few naked Elves.


Cheers,

Brendan

Add that the paging structure (TLB cache) needs to be referenced for every part of an instruction that references memory, and that segmentation can work with a static copy of the current descriptor entry data, and it is a given that paging is many times less efficient than segmentation.

The only reason all of today's major OSes uses paging is for legacy and compatibility reasons. It's certainly not because it is a good solution.

And a smart segmentation implementation would basically never require invalidating descriptors on other CPU cores. Those would be rare things. That's because the OS could avoid reusing selectors, instead allocating them on a random basis. Of course, the selector would be 64 bits, not 16 bits.

Hi,

rdos wrote:Add that the paging structure (TLB cache) needs to be referenced for every part of an instruction that references memory, and that segmentation can work with a static copy of the current descriptor entry data, and it is a given that paging is many times less efficient than segmentation.

Wrong. You're ignoring all of the things that make segmentation bad (memory mapped files, swap space, physical address space de-fragmentation, etc) and focusing on a few negligible things in a deluded attempt at pretending segmentation doesn't suck badly.

rdos wrote:The only reason all of today's major OSes uses paging is for legacy and compatibility reasons. It's certainly not because it is a good solution.

Wrong. In fact it's the exact opposite - OSs use segmentation for backward compatibility, and inevitably break compatibility to remove segmentation in later versions (once they realise the pain of keeping it is worse than the pain of breaking compatibility).

rdos wrote:And a smart segmentation implementation would basically never require invalidating descriptors on other CPU cores. Those would be rare things. That's because the OS could avoid reusing selectors, instead allocating them on a random basis. Of course, the selector would be 64 bits, not 16 bits.

In that case you'd have multiple descriptors referring to the same data, and if the size or access permissions to the data need to be changed you'd be creating new segments on many CPUs rather than invalidating existing segments on many CPUs. It the same problem.

The only alternative that avoid invalidation problems (including "multi-CPU TLB shootdown" and "multi-CPU segment shootdown" and "multi-CPU descriptor recreation") is to refuse to share mutable data between threads/CPUs. Of course "no shared mutable data" has its own (different) problems.


Cheers,

Brendan

Brendan wrote: Wrong. You're ignoring all of the things that make segmentation bad (memory mapped files, swap space, physical address space de-fragmentation, etc) and focusing on a few negligible things in a deluded attempt at pretending segmentation doesn't suck badly.

Using paging to support those is ancient (70s?)

1. Memory mapped files - no reason why this cannot be implemented without paging
2. Swap space - you simply do not support such ancient constructs
3. Physical address defragmentation - not much of a problem when computers have many GB of memory.

Brendan wrote: Wrong. In fact it's the exact opposite - OSs use segmentation for backward compatibility, and inevitably break compatibility to remove segmentation in later versions (once they realise the pain of keeping it is worse than the pain of breaking compatibility).

Not so, popular OS designs (UNIX-compability) requires paging as the whole concept is constructed on top of paging.

rdos wrote:

Brendan wrote: Wrong. In fact it's the exact opposite - OSs use segmentation for backward compatibility, and inevitably break compatibility to remove segmentation in later versions (once they realise the pain of keeping it is worse than the pain of breaking compatibility).

Not so, popular OS designs (UNIX-compability) requires paging as the whole concept is constructed on top of paging.

Ok, now you're definitely frustrated enough to start blatantly lying yet again.