OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Oct 23, 2017 7:30 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 11 posts ] 
Author Message
 Post subject: Shared libraries and resource allocation or exceptions?
PostPosted: Sat Aug 26, 2017 5:57 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 21, 2009 5:54 am
Posts: 172
Location: Moscow, Russia
I have been untangling my kernel code from 7 years ago trying to find a bug, and got to think about improving on an old design decision.

Contemplate a program.
It has some user code, a compiler RTL, a heap and internal state. When the heap space is exhausted, the RTL would call kmalloc to get more space. When that program starts, RTL registers a signal handler for exceptions with the kernel.

Contemplate a shared library.
It got all of the same, that is it also have it's own heap and internal state, and an RTL that would call kmalloc on space exhaustion and register an exception handler on load.

Contemplate the kernel.
It knows which process is active right now, and for every kmalloc call it tracks which process got the memory. This way it can release resources once a process terminates.

Now, there are two problematic scenarios:

Scenario 1. Process P calls a library L function. The function allocates some memory for some external state, runs out of heap space and calls kmalloc. kmalloc sees that current process is P and assigns the memory to it.
Some time later, process P terminates. The kernel deallocates resources assigned to that process, including a part of library L's heap.
Eventually that part would get reused, and L's internal state would get thrashed.

Scenario 2. Process P calls a library L function. The function got a try-except block in it, and something goes really wrong inside, like dereferencing a bad pointer or divide by zero - wrong enough that a CPU exception is thrown. The kernel sees that the current process is P, looks up the signal handler for it and transfers over to it. The P's handler then finds the closest try-except in P and tries to get things fixed.
Thus, L's signal handler and except block is never called, potentially causing an inconsistent state.

How are these problems typically solved?

I have previously solved them by making the linker create a "call gate" on every library function pointer, which would on call and return notify the kernel that we left the current process and entered the library or vice versa, thus enabling it to track stuff properly. It works, but this got a bit of overhead and really looks like a Rube Goldberg machine.

Another solution i contemplated is to add tags to kmalloc/kfree, so that each RTL would have a unique one assigned to it (by kernel on loading), allowing proper resource partitioning. However, that adds a lot of library code and still does not solve the exceptions.

Any better ideas?


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Sat Aug 26, 2017 6:04 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 344
Shared libraries usually share their code and read-only data segments but not their whole data segments or their heaps. Shared libraries share the heap with the process they are running in.

In particular, for ELF the kernel does not even know which shared libraries are used by the process. The user space (i.e. ld.so) is responsible for loading shared libraries and the kernel is only involved in loading ld.so.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Sat Aug 26, 2017 6:32 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 21, 2009 5:54 am
Posts: 172
Location: Moscow, Russia
Korona wrote:
Shared libraries share the heap with the process they are running in.
But then how would it have an internal state?
I.e. a GUI library should be able to track every process's windows and be aware where to pipe the input to, it can't be perfectly local to a single process.

In my design, a library is it's own thing loaded separately, and all linking happens at runtime.
If a process wants to access library functions, it requests an interface for a specific lib and gets a function table.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Sat Aug 26, 2017 6:50 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 344
If you need to share internal state you use IPC or (sometimes) shared memory. You put the input handling into some server that figures out which windows needs to receive a key event and send an IPC message (over a pipe or socket or some other mechanism) to the client library.

Sharing the heap of a shared library sounds extremely fragile. How do you protect the shared state in presence of multiple threads? You'll need mutexes around every global variable. How do you handle thread-local variables in shared libraries? How do you handle malicious (or erroneous) programs that load a shared library and trash its internal state?


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Sat Aug 26, 2017 7:32 am 
Offline
Member
Member

Joined: Fri Aug 19, 2016 10:28 pm
Posts: 199
Artlav wrote:
Korona wrote:
Shared libraries share the heap with the process they are running in.
But then how would it have an internal state?
I.e. a GUI library should be able to track every process's windows and be aware where to pipe the input to, it can't be perfectly local to a single process.

In my design, a library is it's own thing loaded separately, and all linking happens at runtime.
If a process wants to access library functions, it requests an interface for a specific lib and gets a function table.

As Korona noted already, this entire approach has the disadvantage that it exposes the state of multiple unrelated users of the library, which means that one process will be capable of crashing all others. And as Korona already suggested, the proper way to circumvent this (ugly and dissatisfying as it may be) is to create a process whose entire role is to host the shared state and expose it through ipc. The difference in this variant is that the ipc operations are checked, and the global state component associated with a client process can be reclaimed/recovered once this process terminates (which could be detected with heartbeat calls for rpc, or with some monitoring system call.)

On the other hand, on Windows there is a possibility to mark a section as shared in a DLL. This provides you with a globally shared statically allocated state between all client processes, but is outdated practice. In both Windows and Linux, you can map substantial amount of shared memory into a group of processes that you really trust, and then manage the memory inside anyway you wanted. With all the above security caveats.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Sun Aug 27, 2017 3:53 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8116
Location: At his keyboard!
Hi,

Artlav wrote:
Korona wrote:
Shared libraries share the heap with the process they are running in.
But then how would it have an internal state?
I.e. a GUI library should be able to track every process's windows and be aware where to pipe the input to, it can't be perfectly local to a single process.

In my design, a library is it's own thing loaded separately, and all linking happens at runtime.
If a process wants to access library functions, it requests an interface for a specific lib and gets a function table.


Libraries are mostly a (more sophisticated/more complex/more flexible) alternative to "cutting and pasting" source code from a text file of frequently used snippets of code/data directly into the source code of an executable. The library's code becomes part of the executable's code, and the library's data becomes part of the executable's data. They're only separate things until they're linked (and aren't separate pieces after linking, when they're executed).

For your design, to me it sounds like you don't really have libraries but you have something much more like "services" - things with their own independent data and state that don't become part of whichever executable uses it; that communicate via. some sort of IPC (something like remote procedure call in your case, which might even look like a normal function call if the OS uses a "SASOS/Single Address Space" approach and there's no virtual address space switching involved).

A "GUI service" would have internal data (to track every process' windows, figure out where user input gets forwarded, etc) but a GUI library wouldn't. You could have a "GUI library" and a "GUI service" too; where the GUI library could be pure code to make communicating with the GUI service easier, and could also have a process' private data/state that the GUI service doesn't have.

However, what I really think you're trying to do is to merge both concepts (either a service that also has a process's data like a library, or a library that has its own internal data like a service) to create a kind of "libservice". Unless the OS is a SASOS this accidental merging of concepts couldn't have happened (the concepts become incompatible when multiple address spaces are involved and IPC needs to be more than a normal function call).

If my guesses are right; then the solution would be to clearly differentiate between "process data" (for each process using the "libservice") and "service data" that belongs to the "libservice" itself.

In practical terms; for every kmalloc call the kernel tracks which process or which "libservice" got the memory; and a "libservice" would be able to allocate memory for its own internal use (that is not freed when a process is terminated) but would also be able to allocate memory on behalf of a process (that is freed when the process is terminated).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Mon Aug 28, 2017 9:47 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 959
Location: Athens, GA, USA
It sounds to me as if you have the same misunderstanding of shared libraries that I used to have, that they are separate processes that the application process has to call through IPC.

As Brendan states (though I haven't read all of his post yet), this is what is usually called a 'service' - a type of daemon that waits for other processes to request to do something - rather than a shared library.

Now, one thing to be clear about before you can understand this is that in a system with virtual memory, once the read-only portions of a program - the text and rodata sections - are mapped into memory by the loader, they can be used by any process that is running a copy of that program simply by mapping them into that process' virtual memory at the places where they need to be. The virtual memory system maps the code and read-only data for all those processes to the same set of pages in physical memory and/or disk.

The practical upshot of this is that you can have any number of processes running the same program, and while each will need their own heap and stack, they will only need one copy of the code and rodata.

You also need to understand that the code and rodata sections of the process are not necessarily mapped into swap - unless the code needs additional relocation patching at load time, the actual ELF code sections can be used directly. The ELF format was specifically designed for this manner of use, as are most other modern executable object formats.

However, while a given executable can be shared several times, any components that were linked into it when it was created cannot be shared by other programs even if they use the same code - the code inside the completed executable image has already been relocated, and even if the common code avoids all absolute addresses, the loader wouldn't have any way to know which common code was in any two given executables. The process of linking them into a single file loses that information.

This is where shared libraries come in. Shared libraries allow the system to map common code and rodata across different executable images, by keeping them separate until run-time. Since the program has to know that it is using a shared library, and explicitly request that it be loaded, the loader does have the information it needs to share that common code.

More importantly, if things are correctly configured, the loader knows where the shared library is going to be, rather than having to comb through all the executables of the running processes trying to see if there is some piece of code already loaded.

(Note that knowing - or rather, not knowing - where all the shared libraries are, and (not) tracking their versioning in a consistent manner, was the source of the 'DLL Hell' which was the primary impetus for the creation of the Windows Registry. In Linux - and I presume most other Unices which use shared libraries - .so files are usually placed into a shared library path, though this is usually done with symlinks rather than actually saving them to the same directory, I think.)

As long as the shared library doesn't have any load-time global (e.g., not stack or heap) mutable memory of its own, and sticks to using relative and/or indirect addresses, all the loader needs to do is map the shared object file's text and rodata sections into the memory of the first process which uses it, and any which subsequently use once it is loaded; the paging system does all the heavy lifting. The application executables usually don't even need relocation data on the library code - while different programs might require it to be mapped into different virtual locations, they would all map to the same physical pages.

This means, among other things, that there is no separate heap or stack for the shared library code - once the program is loaded, it is no different from the rest of the program.

If you need to share data between two processes, you need to use IPC to synchronize them. This is true whether the data is being used by a shared library or pre-linked executables. However, unless you for some reason have global mutable data in your shared library that isn't allocated on the heap at run-time - something you generally want to avoid - you won't have any such shared data in a shared library. I doubt the ELF format even supports doing that, anyway, but I would need to check.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Last edited by Schol-R-LEA on Tue Aug 29, 2017 10:29 am, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Mon Aug 28, 2017 11:08 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8116
Location: At his keyboard!
Hi,

Brendan wrote:
....


I should probably point out here (mostly because Artlav called it "broken call-gates/franken-lib-services system" in a different post) that (still assuming SASOS - not for other types of OS) I don't see anything wrong with merging the concepts of "library" and "service" into one, don't see any problems it might cause (even for exception unwinding), and could possibly imagine benefits (less pieces for package management to worry about, extra flexibility because different "libservices" are free to use different/incompatible communication between processes).

The only (minor?) disadvantage I can see is that people writing a "libservice" would have to be a little more careful with memory management (making sure they allocate from the right heap) if they use the full potential of "libary and service combined" (if they aren't just implementing "effectively library only" or "effectively service only").


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Tue Aug 29, 2017 10:36 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 959
Location: Athens, GA, USA
Brendan wrote:
I should probably point out here (mostly because Artlav called it "broken call-gates/franken-lib-services system" in a different post) that (still assuming SASOS - not for other types of OS) I don't see anything wrong with merging the concepts of "library" and "service" into one, don't see any problems it might cause (even for exception unwinding), and could possibly imagine benefits (less pieces for package management to worry about, extra flexibility because different "libservices" are free to use different/incompatible communication between processes).


I am going to have to disagree here, because the purposes of the two are quite different IMAO. A library - shared or otherwise - is in effect part of the program; whether there is one address space or several is irrelevant, the important aspect is that library runs as part of the processes using it. A service, OTOH, is something that is separate from its clients; it has its own state, and most often operates as a monitor (in the process synchronization sense) to a shared resource. They are entirely orthogonal concepts.

However, I suspect that - once again - there is a disagreement about definitions here. I would like to hear your thoughts on what you see a service as being, versus a library. From previous posts (I need to go look those up, BRB) I know you dislike the concept of shared libraries, or at least the way they are used in most systems, and I would be interested in hearing your reasons for that as well.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Tue Aug 29, 2017 5:29 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8116
Location: At his keyboard!
Hi,

Schol-R-LEA wrote:
Brendan wrote:
I should probably point out here (mostly because Artlav called it "broken call-gates/franken-lib-services system" in a different post) that (still assuming SASOS - not for other types of OS) I don't see anything wrong with merging the concepts of "library" and "service" into one, don't see any problems it might cause (even for exception unwinding), and could possibly imagine benefits (less pieces for package management to worry about, extra flexibility because different "libservices" are free to use different/incompatible communication between processes).


I am going to have to disagree here, because the purposes of the two are quite different IMAO. A library - shared or otherwise - is in effect part of the program; whether there is one address space or several is irrelevant, the important aspect is that library runs as part of the processes using it. A service, OTOH, is something that is separate from its clients; it has its own state, and most often operates as a monitor (in the process synchronization sense) to a shared resource. They are entirely orthogonal concepts.


The purpose of both is sub-division of work - taking something large and complex and splitting it into smaller (easier to create and maintain, more flexible, more re-usable) pieces.

Sub-division of work is done in a lot of different ways - from the very high level "splitting all software into OS and separate processes" all the way down to fine grained splitting in languages (splitting source code into functions).

There is nothing that says you must sub-divide (at any level) in any specific way. For example; you can think of "megalithic vs. true monolithic vs. modular monolithic vs. hybrid vs. micro-kernel vs. exo-kernel" as just different alternative methods of splitting work. For example; maybe you want to define a program as a set of states, a set of events, and a sequence of actions that occur when an event causes a change to a different state; and you don't have any functions at all. For another example; maybe you want a single extensible machine (LISP machines) and don't want to split things into "processes" at all.

Essentially; libraries and services are just methods of splitting work; and nothing says you can't provide "libservice that's purely a library" and "libservice that's purely a service" and then add a third new "libservice that's a mixture of both library and service" option that programmers could choose if they feel like it.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Shared libraries and resource allocation or exceptions?
PostPosted: Tue Aug 29, 2017 7:07 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 959
Location: Athens, GA, USA
OK, then. That gives me a good handle on your perspective on this. I have some reservations as to how you are characterizing them (in particular, that problem subdivision is the main purpose of services, though I think I see your point in that), both I can accept the basic statement as a working definition.

And you´re certainly right about their being no absolute rules in software development (or at least very few). Hence the need to define terms explicitly. ;-)

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 11 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Alexa [Bot], Alexis211, Google [Bot] and 14 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group