-
Notifications
You must be signed in to change notification settings - Fork 14
/
Copy pathlibrary-implementation.html
142 lines (139 loc) · 9.84 KB
/
library-implementation.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
<!Doctype html>
<html lang="en">
<head>
<title>Library Implementation</title>
<meta charset="UTF-8">
<!--<link rel="stylesheet" href="css/bootstrap.min.css">-->
<link rel="stylesheet" href="css/style_new.css">
<link rel="stylesheet" href="js/embed-2cd369fa1c0830bd3aa06c21d4f14a13e060d2d31bbaae740f4af4.css"><div id="gist28627206" class="gist"></div>
<link rel="stylesheet" href="js/embed-cbe5b40fa72b0964f90d4919c2da8f8f94d7c9f6c2aa49c07f6fa3.css"><div id="gist28627206" class="gist"></div>
<script src="js/jquery-1.12.1.min.js" charset="utf-8"></script>
<script src="js/bootstrap.min.js" charset="utf-8"></script>
<script src="js/sticky_sidebar.js" charset="utf-8"></script>
</head>
<div class="container">
<header id="navtop">
<a href="index.html" class="logo fleft"><img src="img/logo.png" alt=""></a>
<nav class="fright">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="help.html">Help</a></li> -->
<li><a href="roadmap.html">Roadmap</a></li>
<li><a href="documentation.html" class="navactive">Documentation</a></li>
</ul>
</nav>
</header>
<body>
<div class="Services-page main grid-wrap">
<header class="grid col-full">
<hr/>
<p class="fleft">Library Implementation</p>
<br>
</header>
<aside class="grid col-one-quarter mq2-col-full sticky_sidebar" style="position: static;">
<menu>
<ul>
<li><a class="sec" href="#nav-introduction">Introduction</a></li>
<li><a class="sec" href="#nav-illustration">Illustration</a></li>
</ul>
</menu>
<!-- <a class="button" href="">Download as PDF</a> -->
</aside>
<section class="grid col-three-quarters mq2-col-full">
<div class="grid-wrap">
<article class="grid col-full" id="nav-introduction">
<h2>Introduction</h2>
<p>
The ABI stipulates that the code for a <b>common shared library</b> must be linked to the address space of every program. The library code must be linked to logical page 0 and logical page 1 of each program. When an ExpL source program is compiled by an ExpL compiler, the compiler generates code containing calls to the library assuming the library functions will be "there" in the address space when the program is eventually loaded for execution. It is the responsibility of the OS loader to do the actual loading of the library. (In technical jargon, the library is said to be <b><i>linked at compile time</i></b> and <b><i>loaded at run time</i></b>. Unfortunately, there is lack of agreement on terminology in these matters).
</p>
<p>
All calls to the library will be a CALL to logical address 0 of the address space. The library code expects a function code and three arguments to have been pushed into the stack before the call by the application, as described <a href="abi.html#nav-eXpOS-system-library-interface" target="_blank">here</a>.
</p>
<p>
To implement the library, you must write code to implement the six library functions – read, write, exit, Initialize, Alloc and Free. Among these, read, write and exit just involves calling the corresponding system calls using the low-level system call interface described <a href="abi.html#nav-lowlevel-syscall-interface" target="_blank">here</a>. The code for the remaining three functions must be implemented in the library.
</p>
<p>
Initialize, Alloc and Free are <i>heap management functions</i>. Each application program has a heap memory region which is attached to logical pages 2 and 3 of the address space. The heap management functions support allocation and de-allocation of dynamic memory. The <i>Initialize</i> function initializes the heap data structures. The library must contain code to allocate and de-allocate memory when requested by the application. In the case of an allocation request, the address of the first memory address of the allocated memory must be returned.
</p>
<p>
Various dynamic memory allocation algorithms exist. A very simple allocation policy would be to always allocate fixed sized memory blocks. The following document discusses this simple allocation scheme and a more complex variable block allocation method called the <a href="run_data_structures/heap.html#nav-buddy-allocation" target="_blank">Buddy System Allocation</a> scheme. In the project, you will be primarily implementing a fixed size allocator. One of the exercises in the roadmap asks you to implement the buddy system allocator.
</p>
<p>
The advantage of using a library for dynamic memory allocation is that this common code can be loaded by the OS during boot time at some memory and can be attached to the address space of every application, saving memory space.
</p>
<p>
<b>Note</b>: The library implementation outline given below assumes that the application code will modify only memory addresses acquired using <i>Alloc</i>. If the application modifies heap region that was not allocated to it, the data structures set up by the library functions may get corrupted and the library functions may fail to work properly.
</p>
</article>
<article class="grid col-full" id="nav-illustration">
<h2>Illustration</h2>
<p>
The following gives an outline of the library implementation.
</p>
<p>
The ABI stipulates that all the library function calls are invoked using CALL 0 instruction. The library differentiates the calls using function code, pushed by the user program on to the stack, before the CALL 0 instruction. The library should read the function code from the stack and jump to the starting address of the corresponding function logic.
</p>
<p>
The following snippet gives the overview of the design of the library.
<div class="syntax">
//get function code from stack<br>
....<br>
<br>
MOV R0, <function code><br>
MOV R1, R0<br>
EQ R1, "Heapset"<br>
JNZ R1, <starting address of Initialize><br>
MOV R1, R0<br>
EQ R1, "Alloc"<br>
JNZ R1, <starting address of Alloc><br>
....<br>
<br>
// code for Initialize<br>
....<br>
<br>
RET<br>
// code for Alloc<br>
....<br>
<br>
RET<br>
....<br>
</div>
</p>
<p>
As shown above, the function code that was pushed by the application program is used to direct the control of the program to the corresponding function logic. In case of Alloc(), Free() and Initialize() calls, the library contains the logic whereas in case of Read() and Write() system calls the library should invoke the kernel using <a href="abi.html#nav-lowlevel-syscall-interface" target="_blank"> low level system call interface</a>. The appropriate arguments required for the system call can be obtained from the user stack.
</p>
<p>
A detailed explanation on the usage of library interface can be found <a href="xsm-environment-tut.html#nav-experiment3" target="_blank">here</a>.
</p>
<p>
<b>Note:</b> As the library is directly loaded by the ExpOS loader, the code should be free of labels and all the jump instructions should have the target memory addresses.
</p>
</article>
</section>
</div>
</div>
</body>
<footer class="center part clearfix">
<ul class="grid col-one-third social">
<li><a href="http://github.com/silcnitc">Github</a></li>
<li> <a rel="license" href="http://creativecommons.org/licenses/by-nc/4.0/">
<img alt="Creative Commons License" style="border-width:0" src="img/creativecommons.png" /></a></li>
</ul>
<div class="grid col-one-third" style="color:black;">
<p style="font-weight: bold;">Contributed By : <a href="https://www.linkedin.com/in/dattathallam">Thallam Sai Sree Datta</a>, <a href="https://www.linkedin.com/in/n-ruthviik-0a0539100">N Ruthvik</a>
</p>
</div>
<nav class="grid col-one-third ">
<ul >
<li><a href="index.html">Home</a></li>
<li><a href="about.html">About</a></li>
<!-- <li><a href="uc.html">Contact</a></li> -->
</ul>
</nav>
<br>
</footer>
<script>window.jQuery || document.write('<script src="js/jquery-1.7.2.min.js"><\/script>')</script>
<script src="js/scripts.js"></script>
<script src="js/inject.js"></script>
</html>