Shared Libraries / Mapped Files

Shared Libraries / Mapped Files

Shared Libraries

Sharing can be executed at other granularities than individual pages. If a program is started up twice, most operating systems will automatically share all the text pages so that only one copy is in memory. Text pages are always read only, so there is no problem here. Depending on the operating system, each process may get its own private copy of the data pages, or they may be shared and marked read only. If any process changes a data page, a private copy will be made for it, that is, copy on write will be applied.

In current systems, there are many large libraries used by many processes, for instance, the library that handles the dialog for browsing for files to open and multiple graphics libraries. Statically binding all these libraries to every executable program on the disk would make them even more bloated than they already are.

Instead, a common technique is to use shared libraries (which are called DLLs or Dynamic Link Libraries on Windows). To make the idea of a shared library clear, first look at traditional linking. When a program is linked, one or more object files and maybe some libraries are named in the command to the linker, such as the UNIX command



which links all the .0 (object) files in the current directory and then scans two libraries, /usr/lib/libc.a and /usr/lib/libm.a. Any functions called in the object files but not present there (e.g., printf) are called undefined externals and are sought in the libraries. If they are found, they are included in the executable binary. Any functions they call but are not yet present also become undefined externals. For instance, printf needs write, so if write is not already included, the linker will look for it and include it when found. When the linker is done, an executable binary file is written to the disk containing all the functions required. Functions present in the libraries but not called are not included. When the program is loaded into memory and carried out, all the functions it requires are there.

Now assume common programs use 20-50 MB worth of graphics and user interface functions. Statically linking hundreds of programs with all these libraries would waste a tremendous amount of space on the disk as well as wasting space in RAM when they were loaded since the system would have no way of knowing it could share them. This is where shared libraries come in. When a program is linked with shared libraries (which are slightly different than static ones), instead of including the actual function called, the linker includes a small stub routine that binds to the called function at run time. Depending on the system and the configuration details, shared libraries are loaded either when the program is loaded or when functions in them are called for the first time. Certainly, if another program has already loaded the shared library, there is no need to load it again - that is the whole point of it. Note that when a shared library is loaded or used, the entire library is not read into memory in a single blow. It is paged in, page by page, as required, so functions that are not called will not be brought into RAM.

As well as making executable files smaller and saving space in memory, shared libraries have another advantage: if a function in a shared library is updated to remove a bug, it is not necessary to recompile the programs that call it. The old binaries continue to work. This feature is particularly important for commercial software, where the source code is not distributed to the customer. For instance, if Microsoft finds and fixes a security error in some standard DLL, Windows Update will download the new DLL and replace the old one, and all programs that use the DLL will automatically use the new version the next time they are launched.

On the other hand shared libraries come with one little problem that has to be solved. The problem is shown in Figure 1. Here we see two processes sharing a library of size 20 KB (assuming each box is 4 KB). On the other hand, the library is located at a different address in each process, most probably because the programs themselves are not the same size. In process 1, the library starts at address 36K; in process 2 it starts at 12K. Assume that the first thing the first function in the library has to do is jump to address 16 in the library. If the library were not shared, it could be relocated on the fly as it was loaded so that the jump (in process 1) could be to virtual address 36K + 16.  Note that the physical address in the RAM where the library is located does not matter since all the pages are mapped from virtual to physical addresses by the MMU hardware.

Nevertheless, since the library is shared, relocation on the fly will not work. After all, when the first function is called by process 2 (at address 12K), the jump instruction has to go to 12K + 16, not 36K + 16. This is the little problem. One way to solve it is to use copy on write and create new pages for each process sharing the library, relocating them on the fly as they are created, but this scheme defeats the purpose of sharing the library, of course.

A shared library being used by two processes

A better solution is to compile shared libraries with a special compiler flag telling the compiler not to produce any instructions that use absolute addresses. Instead only instructions using relative addresses are used. For instance, there is almost always an instruction that says jump forward (or backward) by n bytes (as opposed to an instruction that gives a specific address to jump to). This instruction works correctly no matter where the shared library is placed in the virtual address space. By avoiding absolute addresses, the problem can be solved. Code that uses only relative offsets is called position-independent code.

Mapped Files

Shared libraries are in fact a special case of a more general facility called memory-mapped files. The idea here is that a process can issue a system call to map a file onto a portion of its virtual address space. In most implementations, no pages are brought in at the time of the mapping, but as pages are touched, they are demand paged in one at a time, using the disk file as the backing store. When the process exits, or explicitly unmaps the file, all the modified pages are written back to the file.

Mapped files provide an alternative model for I/O. Instead of doing reads and writes, the file can be accessed as a big character array in memory. In some situations, programmers find this model more suitable. If two or more processes map onto the same file at the same time, they can communicate over shared memory. Writes done by one process to the shared memory are immediately visible when the other one reads from the part of its virtual address spaced mapped onto the file. This mechanism therefore provides a high-bandwidth channel between processes and is often used as such (even to the extent of mapping a scratch file). Now it should be clear that if memory-mapped files are available, shared libraries can use this mechanism.


Tags

operating system, memory, shared library, undefined externals, address space