[CS61C FA20] Lecture 05.3 - C Memory Management: Memory Locations — Transcript

Full transcript

1. 0:00and welcome back is this fun as we're
2. 0:03going through the series of lectures
3. 0:04we're kind of revealing
4. 0:05the onion revealing the abstraction
5. 0:07layer and explaining how the really the
6. 0:08system works so now i understand how to
7. 0:10play with memory how to require how to
8. 0:11request it either malik how to give it
9. 0:13back and free
10. 0:14really cool but there's some more
11. 0:15details to this let's actually take
12. 0:17take take a reflection of where do
13. 0:20things really live
14. 0:21really live this is really neat this is
15. 0:24people have never seen this before this
16. 0:25is
17. 0:25you don't know this on your own if you
18. 0:26just pick up c on your own you can be
19. 0:28programmed say 100 years but you
20. 0:29wouldn't know the things unless you
21. 0:31get told this i always read the book and
22. 0:33probably tell you but people don't read
23. 0:34the book but if you just kind of pick it
24. 0:35up on your own you're not going to do
25. 0:37so don't forget global variables first
26. 0:40of all so
27. 0:41let's just summarize when you make a
28. 0:43structured declaration
29. 0:44that just declares a new type a
30. 0:47structure that doesn't make any space
31. 0:48for it that's just kind of like here's a
32. 0:49new type i'm going to use
33. 0:51but when you make a variable declaration
34. 0:52that actually does reserve memory so
35. 0:54that the first one doesn't the second
36. 0:55one does reserve
37. 0:57so so far we've talked about several
38. 0:59ways to allocate memory for data you
39. 1:01could have a local variable
40. 1:02int i struck node list that's the node
41. 1:05two fields value and next character star
42. 1:08string
43. 1:08that's the space for the pointer but not
44. 1:10for the string itself int ar of n
45. 1:12there's n integers got that or
46. 1:15dynamically
47. 1:16pointer recall struck node star malik
48. 1:19sizeof struck node
49. 1:20times n that's n nodes in a row there's
50. 1:23an array of nodes rather than a linked
51. 1:25list there's an array
52. 1:26of those of those nodes that's pretty
53. 1:27cool like the struct nodes i should say
54. 1:30there's one more place so one way is a
55. 1:32local variable the second is this maliki
56. 1:34thing
57. 1:35you don't even know where they live yet
58. 1:36i'll tell you that a couple slides and
59. 1:37then finally you could have a global
60. 1:39variable
61. 1:40if i say int global into my global here
62. 1:43above main
63. 1:44so main is your top level procedure
64. 1:46always always in c
65. 1:47but if i put michael above lane it's now
66. 1:50in the global namespace you now have
67. 1:51access to my global everywhere any
68. 1:53subroutine including maine
69. 1:55or sub or foo has access to read and
70. 1:57write my global that's pretty cool so if
71. 1:59you need to have
72. 2:00you know some value that's going to be
73. 2:01shared rather than passing it here
74. 2:03just something that's there just out
75. 2:04there now don't you don't overuse it you
76. 2:06can obviously write the worst code in
77. 2:07the world by having a billion globals
78. 2:09but if you have some constant like a big
79. 2:11table or something you can use that
80. 2:12without having
81. 2:13so gross code although probably it's
82. 2:14better to pass things around but you can
83. 2:16still
84. 2:17you know small programs use global uh
85. 2:19sparingly so use them sparingly
86. 2:21and you'll be fine has global scope so
87. 2:23now
88. 2:24let's use some words use your words
89. 2:27c has three pools of memory okay
90. 2:30remember i had these local guys i had
91. 2:31this mallet guy i had this global guy
92. 2:33turns out that they live in three
93. 2:35different places
94. 2:37the first one static storage that's the
95. 2:40global space it's static
96. 2:42it static means it doesn't dynamic it's
97. 2:44not dynamic it means it's frozen
98. 2:46it does doesn't mean you can't change it
99. 2:47but it means it can't change the size of
100. 2:49it
101. 2:50you can still change the values inside
102. 2:51like my global can be written read and
103. 2:53written to
104. 2:54but that lives in the static so global
105. 2:56variables live there
106. 2:57it's permanent and there for the whole
107. 2:59program so it's not going to grow
108. 3:00okay so static doesn't move the stack is
109. 3:03where your local values are you might
110. 3:05have heard the stack
111. 3:06stack overflow you've never heard how
112. 3:08would it be let me find something on
113. 3:09stack overflow now you know stack
114. 3:11overflow we'll talk about why the stacks
115. 3:12overflow
116. 3:13but you got a stack local variable
117. 3:15storage parameters
118. 3:17return addresses all these things are in
119. 3:20the stack
120. 3:21and the heap is where your mallet goes
121. 3:24so dynamic stuff
122. 3:25is the heap i need to apologize in the
123. 3:28basis of all computer scientists because
124. 3:31the stack the name stack is the same as
125. 3:3561bs a stack data structure
126. 3:38and in fact they operate very much the
127. 3:40same way
128. 3:41okay so they're the same kind of the
129. 3:43idea of the stack in memory
130. 3:45and this what a stack is same thing
131. 3:48the heap is not the same
132. 3:52as the heap data structure so i
133. 3:54apologize on basis of all computer
134. 3:56scientists
135. 3:56what went before me because it's a
136. 3:59terrible
137. 4:00name the heap is not what a heap is it's
138. 4:02not stored it's not
139. 4:03somehow represented using a heap it's
140. 4:04not a heap is just a heap of memory okay
141. 4:08don't think of the heap oh it must be
142. 4:09stored like a heap structure it's not
143. 4:11okay stack is stored like a hashtag
144. 4:13operates like a stack
145. 4:14the heap is not okay c
146. 4:17really fluency requires you to know what
147. 4:19those three things are
148. 4:21this is why i think teaching c to cs1
149. 4:24students to intro programmers
150. 4:25is a terrible idea there's just too much
151. 4:26to learn about how the machine works and
152. 4:28how the code works how debug
153. 4:29too much easier language python blocks
154. 4:31based language something else
155. 4:33but don't teach and see initially third
156. 4:35third language is fine now you know how
157. 4:36to program but i get to
158. 4:37now now you learn how to program well so
159. 4:40here's a picture
160. 4:42the address space contains four regions
161. 4:45this is pretty cool i love this picture
162. 4:47fine line look like revealing the
163. 4:49open the hood there's light shining out
164. 4:50of this okay the stack
165. 4:53local variables remember it starts at
166. 4:55the top
167. 4:56remember roughly you have access to
168. 4:5832-bit machine
169. 5:002 to the 32 0 to 2-3 minus 32-1
170. 5:04bytes that you can read and write okay
171. 5:05for now
172. 5:07stack starts at the top and grows down
173. 5:10poop
174. 5:11so as you have more things as you
175. 5:13increase the stack it's gonna grow down
176. 5:15towards zero
177. 5:18the heap grows up towards this middle
178. 5:22space
179. 5:24static data is locked in you know what
180. 5:25the size of it is it's locked in and in
181. 5:27fact the code
182. 5:29when you run a program if i run foo i
183. 5:31run some program i've run hello world
184. 5:34the code for that gets loaded into
185. 5:35memory as well so that
186. 5:37memory footprint contains all the code
187. 5:41all the static space you have all those
188. 5:42globals
189. 5:44any heap you've requested probably
190. 5:45nothing initially and then
191. 5:47whatever stack has initially probably
192. 5:49has main information here like maybe the
193. 5:51arguments passed in are appear
194. 5:53okay why do we like this model
195. 5:57well it's nice because if i had a
196. 5:58program that had a lot of stack
197. 6:00i had a lot of stackage but a little
198. 6:01heap can you get the inquiry example
199. 6:03like that
200. 6:03what might it be well no heat means that
201. 6:07i never call malik a lot of stack means
202. 6:09maybe a really long recursive maybe a
203. 6:11runaway recursion maybe a
204. 6:13a big fractal or maybe i'm doing
205. 6:14factorial of some huge number
206. 6:16calls this cars cars is because those
207. 6:18local variables all those function calls
208. 6:20grow the stack
209. 6:21okay we'll talk about this we're going
210. 6:23to explain that a little bit more in a
211. 6:24couple slides
212. 6:26how about heap can you think of
213. 6:28something where the heap grows up in
214. 6:29almost no stack well no function calls
215. 6:31so stack is going to grow really no
216. 6:33arrays up there there are no
217. 6:35no temporary variables that are used in
218. 6:36main so the stack is pretty small and i
219. 6:38have the first line is a massive call to
220. 6:40malik
221. 6:41now that he would grow up high do you
222. 6:43know what program would allow you to
223. 6:45have
224. 6:45almost direct control of malik
225. 6:49photoshop i want a new document i want
226. 6:52it one million pixels by one million
227. 6:53pixels
228. 6:54that's no say maybe a thousand by a
229. 6:55thousand that's a million pixels and now
230. 6:57it has to grab it somewhere dynamically
231. 6:59grabs it from the heap another
232. 7:01difference between the heap and stack is
233. 7:04you know ar square brackets that's nice
234. 7:06except that you can't
235. 7:07if i say ar of a million what if i don't
236. 7:09have room for a million
237. 7:10it'll crash but if i ask it through
238. 7:13malik what'll malik return
239. 7:15null so you can now have code that is
240. 7:18resilient to memory failure if you use
241. 7:20it malik
242. 7:21versus using arrays we'll talk about
243. 7:22more but that's kind of an example like
244. 7:24a razor really fast i get it really fast
245. 7:25malik might take a bit longer i'll get
246. 7:27to this at a moment as well
247. 7:28but malik has the ability to tell you if
248. 7:31it can't get it for you whether you
249. 7:32array if you want to make a million
250. 7:34array maybe there's in room at all maybe
251. 7:35you've heaped a lot and now there's no
252. 7:36room here
253. 7:37but it would crash if you say you know
254. 7:39local variable
255. 7:40open square bracket a million you can't
256. 7:42get it crashed there's no way to catch
257. 7:43it there's no way to save it
258. 7:46codes at the bottom static data heap and
259. 7:48the stack okay
260. 7:49important and now but for now don't
261. 7:51worry about how
262. 7:53somebody prevents them from overloading
263. 7:55over crossing each other okay so somehow
264. 7:57that's prevented the os will handle the
265. 7:58take 162
266. 7:59to learn all about it so where are they
267. 8:03allocated i've kind of said before if
268. 8:04they're declared outside of procedure
269. 8:06meaning outside of all procedures my
270. 8:07global they're in the static area
271. 8:09if they're local they're on the stack if
272. 8:12they
273. 8:12are in malik they're on the heap we said
274. 8:14this before and by the way malik is a
275. 8:16procedure
276. 8:17now let's talk about what happens
277. 8:19they're free with the procedure returns
278. 8:20which means wait
279. 8:21so foo calls bar and i get some local
280. 8:23temporary space
281. 8:24when bar goes away it's actually freed
282. 8:26now all that stuff that bar had all
283. 8:27those local variables a bar had
284. 8:29all these arrays that bar had that are
285. 8:30not mallet calls but arrays
286. 8:32they go away when bar returns so that's
287. 8:35actually kind of cool and maine is a
288. 8:36procedure as well
289. 8:38here's your stack let's go a little
290. 8:39deeper on the stack so the stack frame
291. 8:41includes
292. 8:42the return address so how to go back to
293. 8:45the previous guy
294. 8:46important any parameters you have and
295. 8:48space for any local variables
296. 8:50so if you ever like foo calls bar calls
297. 8:52baz you ever wonder how does it know
298. 8:53where to come back to
299. 8:54it's the stack that's how it does it the
300. 8:57other key thing is the stack is
301. 8:58continuous block of memory you'll see
302. 9:00that mallet can actually be all over the
303. 9:02place
304. 9:03it can be uh here and there and there
305. 9:05and that's going to be a problem but the
306. 9:07stack is always continuous
307. 9:08contiguous it grows like a stack unlike
308. 9:11a stack it goes down normally a stack
309. 9:12goes up and you think of it the stack is
310. 9:14going down okay
311. 9:15and the procedure ends the stack frame
312. 9:17is tossed off
313. 9:18so it frees it dynamically pretty cool
314. 9:20so let's actually take a look at this
315. 9:22let's make a little animation
316. 9:24so i'm in maine okay got some space for
317. 9:27maine some local stuff is going on in
318. 9:28maine i'm happy
319. 9:29i call af zero i gotta know where to
320. 9:32come back to
321. 9:32so i gotta i gotta somehow set up i have
322. 9:35to somehow set up a structure where
323. 9:37i need to know when a returns how to
324. 9:40come back to me so i have to store
325. 9:42the line after a0 the line right here
326. 9:44this is the key thing
327. 9:46right there that address that kind of in
328. 9:50that address in the program needs to be
329. 9:51stored somewhere so when a comes back
330. 9:53i reload that's where i'm going to start
331. 9:55from someone's got to remember that and
332. 9:57it's the stack
333. 9:58that's the key so whoops let me erase
334. 10:01this here
335. 10:03okay all right
336. 10:06so now i call a
337. 10:09that's the bottom of the stack pointer
338. 10:10okay i'm going to now make a function
339. 10:12call
340. 10:13so i'm going to grow the stack
341. 10:16i'm going to store my return address and
342. 10:18any temporary any any i'm going to pass
343. 10:20in any parameters here we go
344. 10:21and i've now grown the stack and now
345. 10:23that's where a
346. 10:24is so now main and a are alive and the
347. 10:27stack now has both of those active
348. 10:29and so any temporary variables that are
349. 10:30a are in that area and that's the blue
350. 10:33try to color code them the same so you
351. 10:34can kind of see the same
352. 10:35okay well now a is going to call b
353. 10:38so i better grow the stack move the
354. 10:40stack pointer down
355. 10:41okay by the way that's really fast okay
356. 10:44to do this
357. 10:45i basically take a stack pointer
358. 10:46internally i'll tell you when we learned
359. 10:47about assembly you'll learn about this i
360. 10:49just move the stack printer down it's
361. 10:50really fast okay to grow the stack is
362. 10:52very very fast
363. 10:54and to shrink the stack just move the
364. 10:55stack pointer up pretty easy
365. 10:57okay all this is now the room for b's
366. 11:00local variables any parameters the n has
367. 11:01got to be there somewhere all those
368. 11:03things are there
369. 11:03turns out that the n actually gets
370. 11:05passed as a register too much detail now
371. 11:07but
372. 11:08some space for b to work with okay and
373. 11:10to know how to get back
374. 11:11to a then i go down to c
375. 11:15same thing all we're doing is the same
376. 11:16thing and i go down to d now here's the
377. 11:18key
378. 11:18i'm going to now invert this now d
379. 11:20returns
380. 11:21so watch what happens did i go back into
381. 11:25the code
382. 11:26and erase it grab my eraser and erase
383. 11:28the member to make it all zeros
384. 11:30no the answer is always no i don't have
385. 11:32time no time no time it's almost like no
386. 11:34time no time it's like
387. 11:35my joke about ain't no free lunch no
388. 11:38time no time i'm too busy
389. 11:39i can't erase it so you're gonna notice
390. 11:41interestingly that if d
391. 11:43had some secret value secret value
392. 11:45password
393. 11:46up to the whole world's computer system
394. 11:48equals
395. 11:50bosco and you typed it in the local
396. 11:52variable
397. 11:53so it lived in here somewhere in here
398. 11:56was bosco and now
399. 11:59that was when the stack pointer was
400. 12:01there and now i return from d
401. 12:05and i go back well guess what like by
402. 12:08like the powerpoint shows you it's still
403. 12:10there even though i don't have access to
404. 12:12it official can't be accessing anything
405. 12:13past the stack
406. 12:14bosco is still in memory interesting you
407. 12:18should check that out it's really fun
408. 12:20so now let me clear that up now c
409. 12:22returns
410. 12:24i just move the stack pointer up and
411. 12:26immediately that space isn't
412. 12:27zeroed out but is not space i can use
413. 12:30anymore
414. 12:31okay now b returns and a returns and i'm
415. 12:33still in main doing my stuff
416. 12:35isn't that cool so that's basically how
417. 12:38that notice that was like a stack stack
418. 12:39goes down
419. 12:40stack goes up when you function called
420. 12:41and you return uh
421. 12:43d to c to b to a back into main now
422. 12:46we're living here and now main is
423. 12:47working with all those local variables
424. 12:48doing all the right thing
425. 12:49it's pretty cool and it knew how to get
426. 12:51back because you had the stack the stack
427. 12:52goes
428. 12:53again you learn this all when you learn
429. 12:54about assembly you need to know how to
430. 12:56come back all that's stored in the stack
431. 12:58all the local space is there and you
432. 12:59free it by moving the stack down and
433. 13:00moving stack up
434. 13:01easy see the next lecture