[CS61C FA20] Lecture 13.4 - Compilation, Assembly, Linking, Loading: Linker — Transcript

Full transcript

1. 0:00and welcome back now let's see the third
2. 0:03of our four part series
3. 0:04the linker what does that do for us so
4. 0:07where are we now
5. 0:08the linker is the third stage the
6. 0:10compiler has done its work you've got a
7. 0:11dot s file the assembler's done its work
8. 0:13it's like i got it.o file
9. 0:14you might have a lot of dotto files you
10. 0:16might have library.o files or maybe dot
11. 0:18a files which are library files that
12. 0:19have been wrapped together
13. 0:20into a dot a file which is like a big
14. 0:22package of them all and the linker's job
15. 0:24is to put them all together gather them
16. 0:25all together at the table
17. 0:27and produce an adot out or executable
18. 0:29file
19. 0:31so i just said most of this here you
20. 0:33take the os from the libraries and from
21. 0:35all the user files
22. 0:36the goal is to produce an executable the
23. 0:38process of doing that is called
24. 0:40linking and really the benefit of this
25. 0:42you've seen before
26. 0:43is many different files can be authored
27. 0:47and you don't have to do the whole
28. 0:49process of compiling and assembling them
29. 0:51if you have them all in
30. 0:52os if you only change one file you'll
31. 0:53need to change recompile that one
32. 0:55reassemble that one and then relink the
33. 0:57whole thing together so it's still
34. 0:58linking is the kind of bottleneck of the
35. 1:02whole process where all of those have to
36. 1:03be come together but
37. 1:04the compilation and assembly can be done
38. 1:06only for the small file that got changed
39. 1:08which is really quite nice because some
40. 1:09of these
41. 1:09some of the source or some code linux
42. 1:11photoshop can be really really massive
43. 1:13and
44. 1:13you make one line change you shouldn't
45. 1:15have to do all that work of compiling
46. 1:16assembling all of those
47. 1:17you only have to relink them and i
48. 1:20should say
49. 1:20the old name for this was called the
50. 1:22link editor because the thing that
51. 1:23you're doing is you're fixing all of the
52. 1:25links that are on the relocation table
53. 1:26relocation table says this is the stuff
54. 1:28we didn't know those absolute addresses
55. 1:29yet so
56. 1:30those are the links that i need to fix
57. 1:32and so the link editor linker
58. 1:33comes from the name link editor which is
59. 1:35you're fixing those links from jumping
60. 1:37links
61. 1:38so again each.o file has three parts to
62. 1:41it the dot text
63. 1:42all the code.data which is all the data
64. 1:44and all the information all the
65. 1:46symbol table relocation table debugging
66. 1:48information is in the info
67. 1:49every one of the dot os has that they
68. 1:51all come together from the linker's
69. 1:52point of view and you get an edit out
70. 1:54by taking all the dot all the texts and
71. 1:57put them together you have some order to
72. 1:59them all
73. 1:59so you know the food comes before bar
74. 2:01comes before library let's say foo bar
75. 2:03and some math library okay
76. 2:04so it's foo bar math library text foo
77. 2:07borrow
78. 2:08math library data and then you use the
79. 2:11information to fix those links in there
80. 2:13so that's the idea
81. 2:15so again take that all the text go
82. 2:17together in what order put them together
83. 2:18concatenate them together
84. 2:20put all the data concatenate them
85. 2:21together and then resolve those
86. 2:22references go through that relocation
87. 2:24table
88. 2:25find your symbols and figure out what's
89. 2:26happening and put in the absolute
90. 2:27addresses
91. 2:29four types of addressing you've got pc
92. 2:31relative addressing we
93. 2:32love pc relative addressing because pc
94. 2:34relative means it's position independent
95. 2:36code pic
96. 2:37branch equal branch not equal jowl with
97. 2:40au add upper media pc plus add i all
98. 2:43those things are relative to the pc
99. 2:45and i don't need to worry about that
100. 2:46love that
101. 2:48the other three though we have to always
102. 2:49relocate that's the part the linker's
103. 2:51like oh boy i gotta do some work here
104. 2:53and that's for any absolute function
105. 2:55address so a function call
106. 2:56here that's an absolute call not a
107. 2:58relative call we saw that before
108. 3:00an external function call certainly i
109. 3:02don't know what that is i i mean
110. 3:03even though it might have been the same
111. 3:04call it the same function but if it's
112. 3:06referred for if it's referred to based
113. 3:08on an absolute function still got to
114. 3:09relocate that one
115. 3:10if it's an external function if it's
116. 3:12foo's call bars function
117. 3:13certainly i don't know where bar was in
118. 3:15the final resting place i gotta
119. 3:17get that guy and any static data if i
120. 3:19have any static data that's maybe
121. 3:20relative to the static area i don't know
122. 3:22where the static area was going to be
123. 3:23all that stuff has to be there okay
124. 3:25easy so which instructions need
125. 3:28relocation editing
126. 3:29well jump and link all of those upper
127. 3:32bits here
128. 3:33need to be modified as a result of that
129. 3:37is format this is relative to the static
130. 3:39area this global pointer points to the
131. 3:40beginning of the static area that says
132. 3:42here's where all the static stuff starts
133. 3:44well this is all relative to that that
134. 3:46static area but since i don't know where
135. 3:48the static area is until i finally put
136. 3:50it there
137. 3:51until i finally have text text text text
138. 3:53data data data data that right here is
139. 3:55the beginning of the static area that's
140. 3:56when i now know
141. 3:57uh where that value is and this will be
142. 3:59filled in here and this is going to be
143. 4:01relative to that these values relative
144. 4:02to that
145. 4:03how about conventional branches do i
146. 4:05need to do any work there
147. 4:07no conditional branches are all branch
148. 4:09equal and branch not equal
149. 4:10these are all these conditional things
150. 4:11that are all pc relative position of
151. 4:13independent code
152. 4:14don't need to worry about that these
153. 4:16values would have been filled in there
154. 4:17filled in already these are not
155. 4:18like x's to do's actually they're
156. 4:20usually they set them to zeros but they
157. 4:22said as like to do's that
158. 4:23the final number is there don't need to
159. 4:25worry about those at all i'm pretty good
160. 4:27does it start from zero we always talk
161. 4:29about the code starts at zero
162. 4:30actually the linker assumes the first
163. 4:32word of your first text segment starts
164. 4:34at
165. 4:3410 000 in hex which ends up being 64k
166. 4:38if you think about this each of these
167. 4:39hex is four bits so that's four bits
168. 4:41here four bits here at sixteen so that
169. 4:43means this is two to the sixteenth
170. 4:45so two to the 16th is 64k so it starts
171. 4:47at the 64k place
172. 4:48is where the first text segment ends and
173. 4:50that's like text one text two takes
174. 4:51three
175. 4:52data one data two data three and then
176. 4:54above that is what
177. 4:56sure the heap grows from there and the
178. 4:57stack grows in the top down that's the
179. 4:59idea
180. 5:00the linker knows the length of these
181. 5:01guys all the information in the dot info
182. 5:03in the information file from each of
183. 5:04those
184. 5:05files tells you how long those things
185. 5:07are so now that
186. 5:08now that i know how long they are i'll
187. 5:09go bloop bloop bloop put them in there
188. 5:12and and actually doesn't actually put
189. 5:13them in there until the end but it says
190. 5:15okay that's how long they are so let me
191. 5:16go now fix those
192. 5:18let me fix those links i can i now know
193. 5:19an ordering to them all and i can now
194. 5:21calculate what the absolute address is
195. 5:23and i can now repair
196. 5:24and edit those links so to resolve the
197. 5:27references
198. 5:29i search for a data or label in all the
199. 5:32user symbol tables if you're saying i
200. 5:33want to load some
201. 5:35you know load address well what address
202. 5:37that's a label
203. 5:38okay well let's look for all the labels
204. 5:39and all the symbol tables
205. 5:41you can't find it symbol oh no they'll
206. 5:43say linker symbol.found
207. 5:45if you call a function if you actually
208. 5:47joule call some function that's calling
209. 5:49some maybe external function maybe you
210. 5:52don't have that maybe you didn't include
211. 5:53that library maybe you decided to maybe
212. 5:56you forgot to include the math library
213. 5:58you're calling sign but you didn't
214. 5:59include the math libraries there's no
215. 6:00math.o at all doesn't even know what
216. 6:02math.0 or math.a is
217. 6:03doesn't know what that is at all so it
218. 6:05looks for sign in all the symbol tables
219. 6:06can't find it it'll say symbol unknown
220. 6:08that's great this is also the time when
221. 6:10if you had conflicting names
222. 6:12foo has a function baz bar has a
223. 6:14function baz
224. 6:16independently compiler assembler didn't
225. 6:17know that they were just doing their job
226. 6:19independently just doing my job sir
227. 6:21down here now i've got two bazes it's
228. 6:24two symbol tables now as i'm compiling
229. 6:25all the total symbols that are available
230. 6:27wait i can't have two bars it'll say
231. 6:29conflicting symbol type again that's an
232. 6:30area that only the linker knows about
233. 6:32only when you see all of them together
234. 6:33does i think you know about that once
235. 6:35you're all done once you have all the
236. 6:36absolutes determined you can now write
237. 6:38the final machine code and you're all
238. 6:40done machine code is all i was all done
239. 6:41so the output of this is an eight out
240. 6:45now what i've described so far is a
241. 6:48statically
242. 6:48linked executable it means you load it
243. 6:51on all the data
244. 6:52and text and you put it in there it's
245. 6:54all in a big ball so if i decided to
246. 6:56include the opengl library which is a
247. 6:58really big library a lot of code a lot
248. 6:59of data
249. 7:01well okay i'm putting that in there and
250. 7:02then put this if so my a.o starts to
251. 7:04grow and grow and grow because it's
252. 7:06statically linked it's all linked
253. 7:07together
254. 7:08in the file that's great love that now
255. 7:11all those libraries are part of the
256. 7:12executables
257. 7:13so if i update the libraries i don't to
258. 7:15fix it let's say
259. 7:17i have a new library fix well i don't
260. 7:20get it i have to then recompile that
261. 7:22to uh if i have the source we have to
262. 7:25recompile it to get that library into it
263. 7:26because if you make a new library change
264. 7:28well i this is a baked it i call it
265. 7:31baking in we call it in computer
266. 7:32graphics and in
267. 7:33and in systems i bake it into the thing
268. 7:35it's there it's baked in i can't change
269. 7:37it
270. 7:37um so if i have a new library i can't
271. 7:39get that library oh this new library is
272. 7:41really
273. 7:41ten times faster sorry all my
274. 7:43executables were compiled with
275. 7:44uh the old library i have to now
276. 7:46recompile them that's always a pain
277. 7:48right so if there's
278. 7:49let's say all the source code for every
279. 7:51apple mac os
280. 7:52program is referencing one critical
281. 7:54library and then it has a fix
282. 7:56oh my god every single person every
283. 7:58single developer has to recompile them
284. 7:59and read it and
285. 8:00look app update app update app update
286. 8:03because everybody has to resend that
287. 8:05that's the static model because you bake
288. 8:06those old libraries in and if there's a
289. 8:08change in the library i got to
290. 8:09recompile it and read down and share up
291. 8:11there's an update version
292. 8:120.001 because the new library i used
293. 8:15wasn't
294. 8:15my code didn't work but the library
295. 8:16updated i need to get make sure my users
296. 8:18see that update
297. 8:19because it's more efficient fixes a
298. 8:21security hole whatever while i have to
299. 8:22now resend all those updates to
300. 8:24everybody that's annoying
301. 8:25that's the statically linked model but
302. 8:28the advantage is it's self-contained
303. 8:29that's great the disadvantages
304. 8:33i mean the other model the other model
305. 8:34is a dynamically linked model and the
306. 8:36dynamically link says you know what
307. 8:38let's how about we no what if not what
308. 8:40if we don't
309. 8:41statically link that that library into
310. 8:43the executable what if we just have a
311. 8:46shrinks down to a one liner saying like
312. 8:48pound kind of a pound include
313. 8:49include this library at run time so at
314. 8:52run time it will dynamically link
315. 8:54in the library and then work it out so
316. 8:55that the the loader will then
317. 8:57make it run and do the right thing so it
318. 8:58puts the puts the onus on the loader to
319. 9:00fix it all
320. 9:01at runtime which is interesting this is
321. 9:03called a dll often
322. 9:04in windows system for dynamically linked
323. 9:06library
324. 9:07again what are the advantages of a
325. 9:09dynamically linked library well
326. 9:10my program if i have 20 let's say i have
327. 9:1220 different um
328. 9:1420 different demos from opengl opengl is
329. 9:17a graphics library so you know here's
330. 9:18this
331. 9:19square is moving around and here's
332. 9:20circles moving around here's this maze
333. 9:21blah blah blah here's a 3d
334. 9:23something or ray tracing okay all these
335. 9:25things are showing and highlighting the
336. 9:26opengl library
337. 9:27all 20 demos well as opengl
338. 9:31is changing opengl now has a new version
339. 9:33it's much faster
340. 9:35instantly if i download that new version
341. 9:37of the library
342. 9:38all 20 get a benefit versus having to
343. 9:41now redownload the demos for all 20 and
344. 9:42re or recompile them myself
345. 9:44we can do that as well i could update
346. 9:47one library now the pointer to them so
347. 9:49that's actually quite
348. 9:50interesting rather than a way having
349. 9:51copies that are baked in
350. 9:53i reference it there so that's kind of
351. 9:54nice sending a program requires less
352. 9:57time if i
353. 9:58take all the libraries i used to bloat
354. 9:59my executables smaller now the sudden is
355. 10:01getting downloading programmers faster
356. 10:02maybe
357. 10:03i'm paying for data on my cell phone
358. 10:04service well that's great it's a faster
359. 10:06download love that
360. 10:07also executing two programs requires
361. 10:10less memory
362. 10:11in a way if they share a library you can
363. 10:12be clever about how you actually load
364. 10:14them in so that you don't
365. 10:15you can be referencing the library and
366. 10:17have the library running here and all on
367. 10:18the reference in the library which also
368. 10:19kind of is running as well so that could
369. 10:20be really interesting to pick out
370. 10:21depending how it's done
371. 10:22at runtime now the downside is
372. 10:26at runtime there's less overhead um
373. 10:28there's sorry there's time overhead to
374. 10:29do that link so now when i'm running
375. 10:31rather than go boop i got all the stuff
376. 10:32here just go
377. 10:33now i have to okay go grab oh pound
378. 10:34include where is that okay what's over
379. 10:36here oh there's an error i could have an
380. 10:37error at runtime
381. 10:38that's an issue but it also means that
382. 10:40runtime i have to do do the work of
383. 10:42fixing those links and doing that
384. 10:43at runtime so the startup cost is a
385. 10:45little bit higher run time again but
386. 10:46there's some benefits you saw that
387. 10:48if i have an upgrade i mentioned this
388. 10:49before if i have an upgrade i can just
389. 10:50upgrade the
390. 10:51that lib xyz xyz could be opengl
391. 10:55math anything you want libmath.a is our
392. 10:57math library certainly
393. 10:58you could say lib whatever that is
394. 11:00upgrade that and then just plug that in
395. 11:02and now all of a sudden
396. 11:03everybody gets the benefit of that
397. 11:04that's great but it also means that the
398. 11:06executable isn't enough anymore it means
399. 11:08if i somehow corrupt the math library or
400. 11:10corrupt the opengl library and
401. 11:12my program my 20 programs are using that
402. 11:14none of them will run
403. 11:15they ran yesterday they don't run today
404. 11:17that's a little scary that
405. 11:19i didn't touch it i didn't touch this
406. 11:21executable my machine doesn't touch it
407. 11:23no memory works bus system works
408. 11:24everything works but it doesn't work
409. 11:26anymore why
410. 11:27because somehow my my kid corrupted my
411. 11:29opengl library and now none of my demos
412. 11:31work and now i'm on stage on
413. 11:32tv and then my my demos work that's a
414. 11:35problem you can't really trust your
415. 11:36executables anymore to work
416. 11:37and advance you don't touch them because
417. 11:38your libraries could be touched or i
418. 11:40download the upgrade and the upgrade
419. 11:41kind of quit halfway through i didn't
420. 11:43know that it looks like i got it but i
421. 11:44actually got half a file so now it's
422. 11:45corrupted none of those work
423. 11:46so again you have some trade-off there
424. 11:48from runtime you know it's stable i
425. 11:51downloaded it it's big and bloated but i
426. 11:52know it's going to work versus
427. 11:53it's smaller tighter downloading is
428. 11:55faster i get the free upgrades if i
429. 11:57upgrade that it'll work and i don't just
430. 11:58kind of recompile
431. 11:59but i go to run it and it may not fail
432. 12:02runtime so again there's that
433. 12:03and at the bottom the bottom line says
434. 12:05overall dynamic linking adds quite a bit
435. 12:07of work complexity to the compiler
436. 12:08linker and certainly os which is the
437. 12:10loader but some people find that their
438. 12:12benefits outweigh those costs so that's
439. 12:14pretty cool
440. 12:15so in summary the prevailing approach to
441. 12:18dynamic linking is to link at the lowest
442. 12:20level you don't link at the upper level
443. 12:21let's let's link at the assembler level
444. 12:23no we link at the machine code level i
445. 12:24link at the actual executable
446. 12:26that's going to run i make some room for
447. 12:27it grab the library stuff it in there
448. 12:29and run it like that
449. 12:30so that's again what the loader has to
450. 12:31do and it's a lot harder to do that but
451. 12:33that's the idea you have this lowest
452. 12:34level it's called linking at machine
453. 12:36code level
454. 12:36this isn't the only way to do it but
455. 12:38that's the prevailing model of how they
456. 12:39do linking
457. 12:40dynamically linked code
458. 12:43now we're up to the loader we'll see the
459. 12:45next lecture