>> [MUSIC PLAYING]
>> DAVID J. MALAN: All right.
>> [LAUGHTER]
>> Welcome back.
This is CS50.
And this the end of week five.
And up until now, we've pretty much been taking for granted that there
exists this compiler, Clang, that you've been invoking by way of this
other tool called Make that somehow magically converts your source code
into object code, the zeros and ones that your computers CPU, central
processing unit, actually understands.
But it turns out there's a number that's going on underneath the hood in
between input and output.
>> And I'd like to propose that we flesh that out in a little more detail into
these four steps, have something called pre-processing, something
called compiling, which we have seen, something called assembling, and
something called linking.
So up until now, in some of our programs, we've had sharp includes.
More recently we've had some sharp defines for constants.
So it turns out that those things that are prefixed with the hash symbol or
the pound symbol are pre-processor directives.
That's just a fancy way of saying it's a line of code that's actually
converted into something else before the computer even try to convert your
program into zeros and ones.
>> For instance, sharp includes standard I/O .h, pretty much just means go
ahead, grab the contents of the files stdio.h and paste them right there.
So no zeros and ones at that point yet.
It's really just a substitution.
And that's done during the so-called pre-processing stage, when you
actually run Clang or specifically Make in most cases.
So all this has been happening first automatically thus far.
>> Then comes the compilation step.
But we've been oversimplified compilation.
Compiling a program really means to take it from something like C, the
source code we've been writing, down to something called assembly.
Assembly language is a lower level language that, thankfully, we won't
have much occasion to write this semester.
But it's at the lowest level in the sense that you literally start writing
add and subtract and multiply and load from memory and save to memory, the
very basic instructions that a computer, underneath the hood,
actually understands.
>> Lastly, assembling takes that language to the zeros and ones that we've been
describing thus far.
And truly lastly, there's the so-called linking phase, which we'll
see in just a moment, which combines your zeros and ones with zeros and
ones other people before you have created.
>> So consider this super simple program.
It was from Week 1.
It just said, Hello World, on the screen.
We ran this through Clang.
Or we ran it through Make which ran Clang.
And outputted at the time where some zeros and ones.
But it turns out there's an intermediate step.
If I go over here-- oops, didn't want to see him yet.
If I go over here to my appliance and I open up hello.c, here
is that same program.
And what I'm going to do in my terminal window here is I'm going to
run Clang rather than Make, which automates all four of
those steps for us.
And I'm going to do clang-S and then hello.c and then enter.
>> And I get a blinking prompt again, which is good.
And now in a slightly bigger window, I'm going to open up gedit in here.
And I'm going to open up a file that, turns out, is called hello.s this
contains that assembly language I referred to earlier.
And this is what's called assembly language, fairly low level
instructions that your Intel CPU or whatever it is that's inside
understands.
And mov is for move. call is for calling, a very low level function.
sub is for subtract.
>> So when you have a particular CPU inside of your computer, what makes it
distinct, versus other CPUs on the market, is which instructions it
understands and often how efficient it is, how fast it is at executing some
of those instructions.
Now for more on this, you can take next Fall CS61 at the college.
But here we have, for instance, a few identifiers that might look familiar.
hello.c is the name of the program.
>> .text--
there's not much of interest there just now, recall that the text
segment, as of Monday, is where in memory your program actually ends up.
So that's at least vaguely familiar there.
Here, of course, is a mention of our main function.
Scrolling down, these refer to things called registers, very small chunks of
memory inside of your actual CPU.
And if I scroll down even further, I see some sort
indirect mention of ASCII.
And there, indeed, is that string, hello, comma, world.
>> So long story short, this has been happening for you, automatically,
underneath the hood all of this time.
And what's been happening really is once you've run Clang, or by way of
Make, you're getting first, from the source code, the
so-called assembly language.
Then Clang is converting this assembly language down to zeros and ones.
And this is the slide that we started our discussion in Week 0 on--
and then Week 1 on.
And then finally, those zeros and ones are combined with the zeros and ones
from those libraries we've been taking for granted like Standard I/O or the
String Library or even the CS50 library.
>> So to paint this picture more visually, we have hello.c.
And it, of course, uses the printf function to say, hello world.
The compilation step takes it down to that file we just saw hello.s, even
though that's typically deleted automatically for you.
But that's the assembly code in the middle step.
And then when we assemble the assembly language, so to speak, that's when you
get those zeros and ones.
So we've zoomed in effectively today on what we've been taking for granted,
means going source code to object code.
>> But lastly, now that same picture-- let's shove it over to
the left hand side.
And note that in the top there I mentioned stdio.h.
That's a file that we've included in almost all of the
programs we've written.
And that's the file whose contents get copy pasted,
effectively atop your code.
But it turns out that, on a computer system somewhere, there's presumably a
stdio.c file that someone wrote years ago that implements all of the
functions that were declared in stdio.h.
>> Now in reality it's probably not on your Mac or your PC or even in the
CS50 appliance is a raw C code.
Someone already compiled it and included .o file for object code or .a
file, which refers to a shared library that's been pre-installed and
pre-compiled for you.
But suppose that there indeed exists on our computer stdio.c in parallel
with Clang.
Your code's being compiled and assembled.
stdio.c's code is being compiled and assembled, so that this very last
step, down here, we have to somehow link, so to speak, your zeros and ones
with his or her zeros and ones into one simple program that ultimately is
called just Hello.
>> So that's all of the magic that's been happening thus far.
And will continue to take these processes for granted, but realize
there's a lot of juicy details going on underneath there.
And this is what makes your computer with Intel inside
particularly distinct.
>> So on that note, if you would like to join us for lunch this Friday, do go
to the usual place cs50.net/rsvp, 1:15 PM this Friday.
And now a few announcements.
So we have some good news.
And we have some bad news.
Start with some good news here.
>> [GROANING]
>> All right.
Well, it's technically a holiday, so it's not so much a gift from us.
But then the bad news of course.
>> [GROANING]
>> I spent a lot of time on these animations.
>> [LAUGHTER]
>> There will be a review session this coming Monday.
It's going to be at 5:30 PM.
We will remind you of all these details via email on the course's
website in just a couple of days time.
It will be filmed and made available shortly thereafter.
So if you can't make that Monday night slot, don't worry.
Sections this coming week will also focus on review for the quiz.
If your section is on Monday, which is indeed university holiday, we will
still meet in section.
If you simply can't make that section because you're going
away, that's fine.
Attend a Sunday or Tuesday section or tune-in to Jason's section, which is
available online.
>> So, more bad news.
So according to the syllabus, we have lecture next Friday.
But the good news--
clearly, I spent too much time on this.
>> [LAUGHTER]
>> We'll cancel next Friday's lectures.
So that will be a gift for us, so you can really have a nice respite in
between this week and two weeks hence.
So no lectures next week, just a tiny little quiz, for which you should be
getting increasingly excited.
>> So let's now turn our attention to something that is indeed more visual
and more exciting and to set the stage for what's going to be on the horizon
in just a couple of weeks time.
After the first quiz, we'll turn the focus of our problem sets to another
domain specific problem, that of forensics or security more generally.
>> In fact, the tradition with this problem set is for me one of the
teaching fellow or CAs to walk across campus taking some photographs of
identifiable but non obvious people, places, or things, then every year I
somehow manage to accidentally delete or corrupt the digital media card
that's inside of our camera.
But no big deal.
I can go ahead and plug that into my computer.
I can make a forensic image of it, so to speak, by copying the zeros and
ones off of that memory card, whether its a SD card or compact flash card or
whatever you're familiar with.
And then we can hand that out.
>> And so the challenge ahead, among other things for you, will be to write
C code that recovers a whole bunch of JPEGs for me and revealed will be
those people, places, or things.
And we'll also talk, in this problem set and in the days to come, about
graphics more generally.
We've used them, a course, for break out.
But you've sort of taken for granted there exists these high level notions
of rectangles and ovals.
But underneath the hood there are pixels.
And you have had to start thinking about those.
Or you will for p-set 4 have to think about the gap between your bricks, how
quickly you're ball is moving across the screen for break out.
So there is this notion of the dots on your screen that's
come into play already.
>> Now what you see, though, is what you get on a computer screen.
If you've ever watched some good or bad TV, odds are they pretty much
treat the audience like technophobes who don't really
know much about computing.
And so it's very easy for the police detective to say, can you
clean that up for me?
Or enhance, right?
Enhance is like the buzz word in most any crime related show.
And the reality is if you take a very blurry picture of a suspect doing
something bad, you cannot just enhance it.
You cannot zoom in infinitely.
You cannot see in the glint of someone's eye who committed that
particular crime, despite the prevalence of this on TV.
>> And so with that let's motivate that upcoming problem set with a glimpse at
some shows with which you might be familiar.
>> [VIDEO PLAYBACK]
>> -OK.
Now, let's get a good look at you.
>> -Hold it.
Run that back.
>> -Wait a minute.
Go right.
>> -There.
Freeze that.
>> -Full screen.
>> -OK.
Freeze that.
>> -Tighten up on that, will ya?
>> -Vector in on that guy by the back wheel.
>> -Zoom in right here on this spot.
>> -With the right equipment, the imaged can be enlarged and sharpened.
>> -What's that?
>> -It's an enhancement program.
>> -Can you clear that up any?
>> -I don't know.
Let's enhance it.
>> -Enhance section A-6.
>> -I enhanced the detail and--
>> -I think there's enough to enhance.
Release it to my screen.
>> -Enhance the reflection in her eye.
>> -Let's run this through video enhancement.
>> -Edgar, can you enhance this?
>> -Hang on.
>> -I've been working on this reflection.
>> -Someone's reflection.
>> -Reflection.
>> -There's a reflection of the man's face.
>> -The reflection.
>> -There's a reflection.
>> -Zoom in on the mirror.
>> -You can see a reflection.
>> -Can you enhance the image from here?
>> -Can you enhance him right here?
>> -Can you enhance it?
>> -Can we enhance this?
>> -Can you enhance it?
>> -Hold on a second, I'll enhance.
>> -Zoom in on the door.
>> -x10.
>> -Zoom.
>> [LAUGHTER]
>> -Move in.
>> -Wait, stop.
>> -Stop.
>> -Pause it.
>> -Rotate a 75 degrees around the vertical please.
>> [LAUGHTER]
>> -Stop, and back to the part about the door again.
>> -Got an image enhancer that can bitmap?
>> -Maybe we can use the Pradeep Sen method to see into the windows.
>> -This software is state of the art.
>> -The icon value is off.
>> -With the right combination of algorithms.
>> -He's taken illumination algorithms to the next level and I can use them to
enhance this photograph.
>> -Lock on and enlarge the z-axis.
>> -Enhance.
>> -Freeze and enhance.
>> [END VIDEO PLAYBACK]
>> DAVID J. MALAN: So Problem Set 5 is what lies ahead there.
So we'll soon get a better understanding of when and why you can
and our cannot enhance in that way.
But first, let's return our attention to some of the building blocks we'll
need to be able to tell that story.
>> So recall that we drew this picture on Monday and a little bit last week.
And this describes the layout of things in your computer's memory when
running some program.
The tech segment up top, recall, refers to the actual zeros and ones
that compose your program.
There's, below that, some initialized or uninitialized data, which typically
refers to things like constants or strings or global variables that have
been declared in advance.
There's the heap, but we'll come back to that in a bit.
>> And then there's the stack.
Much like a stack of trays in the cafeteria, this is where memory gets
layered and layered whenever you do what in a program?
What is the stack use for?
>> Yeah?
>> Call of function.
Any time you call a function, it's given to sliver of memory for its
local variables or its parameters.
And pictorially, we see that with each successive function called, when A
calls B calls C calls D, they get layered onto the stack.
And within each of those slices of memory is essentially a unique scope
for that function, which, of course, is problematic if you want to hand
from one function to another A piece of data that you want it
to mutate or change.
>> So what was our solution to enabling A function represented by one stack
frame to change the memory inside of another stack frame?
How do those two talk to one another?
So by way of pointers or addresses, which, again, just describe where in
memory, by way of a specific bite number, the particular
value can be found.
So recall last time too we continued the story and looked at a
fairly buggy program.
And this program is buggy for a few reasons, but the most worrisome one is
because it fails to check what?
>> Yeah, it fails to check the input.
Sorry?
>> If it's more than 12 characters.
So very smartly, when calling memcopy, which, as the name suggests, just
copies memory from its second argument into its first argument.
The third argument, very smartly, is checked to make sure that you don't
copy more than, in this case, the length of bar, number of characters,
into the destination, which is this array C. But the problem is that what
if C itself is not big enough to handle that?
You're going to copy the number of bytes that you've been given.
But what do you actually have more bytes than you have room for?
>> Well, this program very foolishly just blindly proceeds to take whatever it's
given, hello backslash 0 is great if string is short
enough, like five chars.
But if it's actually 12 characters or 1,200 characters, we saw last time
that you're just going to completely overwrite memory that
doesn't belong to you.
And worst case, if you overwrite that red portion there that we called the
return address--
this is just where the computer automatically, for you, behind the
scenes, tucks away a 32-bit value that reminds it to what address it should
return when foo, this other function, is done executing.
It's a bread crumb of sorts to which it returns.
If you overwrite that, potentially, if you're the bad guy, can could
potentially take over someone's computer.
And you'll most certainly crash it in most cases.
>> Now this problem was only exacerbated as we started talking about memory
management more generally.
And malloc, for memory allocation, is a function that we can use to allocate
memory when we don't know in advance that we might need some.
So, for instance, if I go back to the appliance here.
And I open up from last time hello2.c, recall this program here, which looked
a little something like this, just three lines--
state your name, then string name, on the left, equals getstring.
And then we print it out, the user's name.
>> So this was a super simple program.
To be clear, let me go ahead and make hello-2.
I'm going to do dot slash hello-2.
State your name--
David.
Enter.
Hello David.
It seems to work OK.
But what's really going on underneath hood here?
First let's peel back some layers.
String is just a synonym we've realized for what?
Char star.
So let's make it a little more arcane but more technically correct that this
is a char star, which means that name, yes, is a variable.
But what name stores is the address of a char, which feels a little strange
because I'm getting back a string.
I'm getting back multiple chars not a char.
>> But of course, you only need the first char's address to remember where the
whole string is because why?
How do you figure out where the end of the string is knowing the beginning?
The backslash zero.
So with those two clues you figure out before the beginning and the end of
any string are, so long as they're properly formed with that null
terminator, that backslash zero.
>> But this is calling getstring.
And it turns out that getstring all this time has been kind of
cheating for us.
It's been doing this labor, to be sure, getting a string from the user.
But where's that memory been coming from?
If we go back to the picture here and apply the definition from just a
moment ago, that the stack is where memory goes when functions are called,
by that logic, when you call getstring, and then I type in
D-A-V-I-D Enter, where is D-A-V-I-D backslash zero stored, based on the
story we've told us far?
>> It would seem to be in the stack, right?
When you call get string you get a little slice of memory on the stack.
So it stands to reason that D-A-V-I-D backslash zero is stored
there in the stack.
But wait a minute, getstring returns that string, so to speak, which means
it's tray from the cafeteria is taken off the stack.
And we said last time that as soon as a function returns, and you take that
tray, so to speak, off the stack, what can you assume about the remnants of
that memory?
I sort of redrew them as question marks because they effectively become
unknown values.
They can be reused when some next function is called.
>> In other words, if we happen to be storing--
I'll draw a quick picture here of the stack.
If we happen to be drawing the bottom of my memory segment, and we'll say
that this is the place of memory occupied by main and maybe arg c and
arg v and anything else in the program, when getstring is called,
presumably getstring gets a chunk of memory here.
And then D-A-V-I-D somehow ends up in this function.
And I'm going to oversimplify.
But let's assume that its D-A-V-I-D backslash zero.
So this many bytes are used in the frame for getstring.
>> But as soon as getstring returns, we said last time that this memory over
here all becomes --woops!--
all becomes effectively erased.
And we can think of this now as question marks because who knows
what's going to become of that memory.
Indeed, I very often call functions other than getstring.
And as soon as I call some other function than getstring, maybe not in
this particular program we just looked at but some other, surely some other
function might end up being given this next spot in the stack.
>> So it can't be that getstring stores D-A-V-I-D on the stack because I would
immediately lose access to it.
But we know they getstring only returns what?
It's not returning to me six characters.
What is it truly returning did we conclude last time?
The address of the first.
So somehow, when you called getstring, it's allocating a chunk of memory for
the string that the users type and then returning address of it.
And it turns out that when you want to function to allocate memory in this
way and return to the person who called that function, the address of
that chunk of memory, you absolutely can't put it in the stack at the
bottom, because functionally it's just going to not become yours very
quickly, so you can probably guess where we're probably going to toss it
instead, the so-called heap.
>> So between the bottom of your memory's layout and the top of your memory's
layout are a whole bunch of segments.
One is the stack, and right above it is the heap.
And heap is just a different chunk of memory that's not used for functions
when they're called.
It's used for longer term memory, when you want one function to grab some
memory and be able to hang on to it without losing control over it.
>> Now you could perhaps immediately see that this is not
necessarily a perfect design.
As your program allocated memory on the stack, or as you call more and
more functions, or as you allocate memory on the heap with malloc off as
getstring is doing, what clearly seems to be inevitable problem?
>> Right.
Like the fact that these arrows are pointing at each other
does not bode well.
And indeed, we could very quickly crash a program in any number of ways.
In fact, I think we might have done this accidentally once.
Or if not, let's do it deliberately now.
Let me go ahead and write super quickly a program called dontdothis.c.
And now I'll go in here and do sharp include stdio.h.
Let's declare function foo takes no arguments, which is
denoted as well by void.
>> And the only thing foo is going to do is call foo, which probably isn't the
smartest idea, but so be it.
Ent main void.
Now the only thing main is going to do is call foo as well.
And just for kicks, I'm going to go ahead here and say printf "Hello from
foo."
>> OK.
So if I didn't make any mistakes, Make dontdothis dot slash.
And let's do it in a bigger window--
dot slash, dontdothis.
Come on.
Uh oh.
Apparently, you can do this.
Damn it.
OK.
Wait.
Stand by.
Did we--
We did use it with Make.
>> [SIGHS]
>> I know but I think we just deleted that.
Uh, yeah.
Damn it.
Solve this Rob.
What?
It's very simple.
Yeah, we turned optimization off.
OK, stand bye.
Now I feel better.
OK.
All right.
>> So let's recompile this--
Make you dontdothis.
You might have to rename this to dothis.c in just a moment.
There we go.
Thank you.
OK.
So the fact that I was printing something out was actually just
slowing down the process by which we would have reached that point.
OK.
Phew!
>> So what is actually going on?
The reason there, just as an aside, is doing anything in terms of input and
output tends to be slower because you have to write characters to the
screen, It has to scroll.
So long story short, had I actually happened so impatient, we would have
seen this end result as well.
Now that I got ride of the print-ups, we see it right away.
So why is this happening.
Well, the simple explanation, of course, is that foo probably shouldn't
be calling itself.
>> Now in general terms, this is recursion.
And we thought a couple weeks ago recursive is good.
Recursion is this magical way of expressing yourself super succinctly.
And it just works.
But there is a key feature of all of the recursive programs we've talked
about and looked at thus far, which was that they had what?
A base case, which was some hard coded case that said in some situations
don't call foo, which is clearly not the case here.
>> So what is really happening in terms of this picture?
Well, when main calls foo, it gets a slice of memory.
When foo calls foo, it gets a slice of memory.
When foo calls foo, it gets a slice.
It gets a slice.
Because foo is never returning.
We're never erasing one of those frames from the stack.
So we're blowing through the heap, not to mention who knows what else, and
we're overstepping the bounds of our so-called segment of memory.
Error go segmentation false.
>> So the solution there is clearly don't do this.
But the bigger implication is that, yes, there absolutely is some limit,
even if it's not well defined, as to how many functions you can call in a
program, how many times a function can call itself.
So even though we did preach recursion as this potentially magical thing a
couple of weeks ago for the sigma function, and when we get the data
structures and CS50, you'll see other applications for it, it's not
necessarily the best thing.
Because if a function calls itself, calls itself, even if there's a base
case, if you don't hit that base case for 1,000 calls or 10,000 calls, by
that time you might have run out of room on your so-called stack and hit
some other segments of memory.
So it too is a design trade-off between elegance and between
robustness of your particular implementation.
>> So there's another downside or another gotcha to what we've
been doing thus far.
When I called getstring--
let me go back into hello-2.
Notice that I'm calling getstring, which is returning an address.
And we claim today that address is from the heap.
And now I am printing out the string at that address.
But we've never called the opposite of getstring.
We've never had to calll a function like ungetstring, where you hand back
that memory.
But frankly we probably should have been.
Because if we keep asking the computer for memory, by way of someone like
getstring but never give it back, surely that too is bound to lead to
problems whereby we run out of memory.
>> And in fact, we can look for these problems with the new tool whose usage
is a little cryptic to type.
But let me go ahead and splash it up on the screen in just a moment.
I'm going to go ahead and run Valgrind with parameter whose first command
line argument is the name of that program hello-2.
And unfortunately it's output is atrociously
complex for no good reason.
So we see all that mess.
David is state my name.
So that's the program actually running.
And now we get this output.
>> So Valgrind is similar in spirit to GDB.
It's not a debugger per se.
But it's a memory checker.
It's a program that will run your program and tell you if you asked a
computer for memory and never handed it back, thereby meaning that you have
a memory leak.
And memory leaks tend to be bad.
And you is users of computers have probably felt this, whether you have a
Mac or a PC.
Have you ever used your computer for while and not rebooted in several
days, or you've just got a lot of programs running, and the damn thing
slows to a grinding halt, or at least it's super annoying to use, because
everything just got super slow.
>> Now that can be any number of reasons.
It could be an infinite loop, a bug in someone's code, or, more simply, it
could mean that you're using more memory, or trying to, than your
computer actually has.
And maybe there's a bug in some program that keep asking for memory.
Browsers for years were notorious for this, asking for more and more memory
but never handing it back.
Surely, if you only have a finite amount of memory, you can't ask
infinitely many times for some of that memory.
>> And so what you see here, even though again Valgrind's output is
unnecessarily complex to glance at first, this is the interesting part.
Heap --
in use at exit.
So here's how much memory was in use in the heap at the
time my program exited--
apparently six bytes in one block.
So I'm going to wave my hands at what a block is.
Think of it is just a chunk, a more technical word for chunk.
But six bytes--
what are the six bytes that were still in use?
>> Exactly.
D-A-V-I-D backslash zero, five letter name plus the null terminator.
So this program Valgrind noticed that I asked for six bytes, apparently, by
way of getstring, but never gave them back.
And in fact, this might not be so obvious if my program isn't three
lines, but it's 300 lines.
So we can actually give another command line argument to Valgrind to
make it more verbose.
It's a little annoying to remember.
But if I do--
let's see.
Leak--
Was it leak--
even I don't remember what it is off hand.
>> --leak-check equals full.
Yep, thank you.
--leak-check equals full.
Enter.
Same program is running.
Type in David again.
Now I see a little more detail.
But below the heap summary, which is identical to four-- ah,
this is kind of nice.
Now Valgrind is actually looking a little harder in my code.
And it's saying that, apparently, malloc at line--
we zoom out.
At line--
we don't see what line it is.
But malloc is the first culprit.
There's a blog in malloc.
>> All right?
OK, no.
Right?
I called getstring.
getstring apparently calls malloc.
So what line of code is apparently at fault for having
allocated this memory?
Let's assume that whoever wrote malloc has been around long enough that it's
not their fault.
So it's probably mine.
getstring in cs50.c --so that's a file somewhere on the computer--
in line 286 seems to be the culprit.
Now let's assume that cs50 has been around for decent amount of time, so
we too are infallible.
And so it's probably not in getstring that the bug lies, but rather in
hello-2.c line 18.
>> So let's take a look at what that line 18 was.
Oh.
Somehow this line isn't necessarily buggy, per se, but it is the reason
behind that memory leak.
So super simply, what would intuitively be the solution here?
If we're asking for memory, were never giving it back, and that seems to be a
problem because over time my computer might run out of memory, might slow
down, bad things might happen, well, what's the simple intuitive solution?
Just give it back.
>> How do you free up that memory?
Well, thankfully it's quite simple to just say free name.
And we've never done this before.
But you can essentially think of free as the opposite of malloc.
free is the opposite of allocating memory.
So now let me recompile this.
Make hello-2.
Let me run it again. hello-2 David.
So it seems to work in exactly the same way.
But if I go back to Valgrind and re-run that same command on my newly
compiled program, typing in my name as before--
nice.
Heap summary--
in use at exit--
zero bytes in zero blocks.
And this is super nice, all heap blocks were freed.
No leaks are possible.
>> So coming up, not with Problem Set 4, but with Problem Set 5, the forensics
and onward, this too will become a measure of the correctness of your
program, whether or not you have or don't have memory leaks.
But thankfully, not only can you reason through them intuitively, which
is, arguably, easy for small programs but harder for larger programs,
Valgrind, for those larger programs, can help you identify
the particular problem.
>> But there's one other problem that might arise.
Let me open up this file here, which is, again, a somewhat simple example.
But let's focus on what this program does.
This is called memory.c.
We'll post this later today in the zip of today's source code.
And notice that I have a function called f that takes no arguments and
returns nothing.
In line 20, I'm apparently declaring a pointer to an int and calling it x.
I'm assigning is the return value of malloc.
And just to be clear, how many bytes am I probably getting back from malloc
in this situation?
>> Probably 40.
Where do you get that from?
Well, if you recall that an int is often 4 bytes, at least it is in the
appliance, 10 times 4 is obviously 40.
So malloc is returning an address of a chunk of memory and storing that
address ultimately in x.
So to be clear, what then is happening?
Well, let me switch back to our picture here.
Let me not just draw the bottom of my computer's memory, let me go ahead and
draw the whole rectangle that represents all of my RAM.
>> We'll say that the stack is on the bottom.
And there's a text segment in the uninitialized data.
But I'm just going to abstract those other things away as dot, dot dot.
I'm just going to refer to this as the heap at the top.
And then at the bottom of this picture, to represent main, I'm going
to give it a slices memory on the stack.
For f, I'm going to give it a slice of memory on the stack.
Now, I got to consult my source code again.
What are the local variables for main?
Apparently nothing, so that slice is effectively empty or not even as big
as I've drawn it.
But in f, I have a local variable, which is called x.
So I'm going to go ahead and give f a chunk of memory, calling it x.
>> And now malloc of 10 times 4, So malloc 40, where's that
memory coming from?
We've not drawn a picture like this before.
But let's suppose that it's effectively coming from here, so one,
two, three, four, five.
And now I need 40 of these.
So I'll just do dot, dot, dot to suggest that there's even more memory
coming back from the heap.
Now what's the address?
Let's choose our arbitrary address as always--
Ox123, even though it's probably going to be something completely different.
That's the address of the first byte in memory that I'm asking malloc for.
>> So in short, once line 20 executes, what is literally
stored inside of x here?
Ox123.
And the Ox is uninteresting.
It just means here's a hexadecimal number.
But what's key is that what I've store in x, which is a local variable.
But its data type, again, is an address of an int.
Well, I'm going to store Ox123.
But again, if that's a little too complicated unnecessarily, if I scroll
back, we can abstract this away quite reasonably and just say that x is a
pointer to that chunk of memory.
>> OK.
Now the question at hand is the following--
line 21, it turns out, is buggy.
Why?
>> Sorry?
It doesn't have--
say that once more.
Well, it doesn't free.
So that's the second but.
So there's one other but specifically at line 21.
>> Exactly.
This simple line of code is just a buffer overflow, a buffer overrun.
A buffer just means a chunk of memory.
But that chunk of memory is of size 10, 10 integers, which means if we
index into it using the syntactic sugar of array notation, the square
brackets, you have access to x bracket 0 x bracket 1 x,
bracket dot, dot, dot.
x bracket 9 is the biggest one.
So if I do x bracket 10, where I'm actually going in memory?
>> Well, if I have 10 int--
let's actually draw all of these out here.
So that was the first five.
Here's the other five ints.
So x bracket 0 is here. x bracket 1 is here. x bracket 9 is here. x bracket
10 is here, which means I am telling, in line 21, the computer to put the
number where?
The number 0 where?
Well, it's 0, yes.
But just the fact that its 0 is kind of a coincidence.
It could be the number 50, for all we care.
But we're trying to put it at x bracket 10, which is where this
question mark is drawn, which is not a good thing.
This program might very well crash as a result.
>> Now, let's go ahead and see if this is, indeed, what happens.
Make memory, since the file is called memory.c.
Let's go ahead and run the program memory.
So we got lucky, actually, it seems.
We got lucky.
But let's see if we now run Valgrind.
At first glance, my program might seem to be perfectly correct.
But let me run Valgrind with the --leak-check equals full on memory.
>> And now when I run this--
interesting.
Invalid write of size 4 at line 21 of memory.c.
Line 21 of memory.c is which one?
Oh, interesting.
But wait.
Size 4, what is that referring to?
I only did one write, but it's of size 4.
Why is it 4?
It's because it's an int, which is, again, four bytes.
So Valgrind found a bug that I, glancing at my code, didn't.
And maybe your TF would or wouldn't.
What But Valgrind for sure found that we've made a mistake there, even
though we got lucky, and the computer decided, eh, I'm not going to crash
just because you touched one byte, one int's worth of memory that you didn't
actually own.
>> Well, what else is buggy here.
Address--
this is a crazy looking address in hexadecimal.
That just means somewhere in the heap is zero bytes after a block of size 40
is allocated.
Let me zoom out here and see if this is a little more helpful.
Interesting.
40 bytes are definitely lost in loss record 1 of 1.
Again, more words than is useful here.
But based on the highlighted lines, where should I probably focus my
attention for another bug?
Looks like a line 20 of memory.c.
>> So if we go back to line 20, that's the one that you identified earlier.
And it's not necessarily buggy.
But we have this reversed its effects.
So how do I correct at least one of those mistakes?
What could I do after line 21?
I could do free of x, so is to give back that memory.
And how do I fix this bug?
I should definitely go no farther than 0.
So let me try and re-run this.
Sorry, definitely go no farther than 9.
Make memory.
Let me rerun Valgrind in a bigger window.
And now look.
Nice.
All heap blocks were freed.
No leaks are possible.
And up above here, there's no mention any more of the invalid right.
>> Just to get greedy, and let's see if another demonstration
does not go as intended--
I did get lucky a moment ago.
And the fact that this is 0 is perhaps unnecessarily misleading.
Let's just do 50, a somewhat arbitrary number, make memory dot slash memory--
still get lucky.
Nothing's crashing.
Suppose I just do something really foolish, and I do 100.
Let me remake memory, dot slash memory--
got lucky again.
How about 1,000?
ints beyond, roughly, where I should be?
Make memory--
damn it.
>> [LAUGHTER]
>> OK.
Let's not mess around anymore.
Rerun memory.
There we go.
All right.
So apparently you index 100,000 ints beyond where you should have been in
memory, bad things happen.
So this is obviously not a hard, fast rule.
I was kind of using trial and error to get there.
But this is because, long story short, your computer's memory is also divided
into these things called segments.
And sometimes, the computer actually has given you a little more memory
than you ask for.
But for efficiency, it's just easier to get more memory but only tell you
that you're getting a portion of it.
>> And if you get lucky sometimes, therefore, you might be able to touch
memory that doesn't belong to you.
You have no guarantee that what value you put there will stay there, because
the computer still thinks it's not yours, but it's not necessarily going
to hit another segment of memory in the computer and induce a mistake like
this one here.
All right.
Any questions then on memory?
>> All right.
Let's take a look here, then, at something we've been taking for
granted for quite some time, which is in this file called cs50.h.
So this is a file.
These are just a whole bunch of comments up top.
And you might have looked at this if you poked around on the appliance.
But it turns out that all the time, when we used to use string as a
synonym, the means by which we declared that synonym was with this
keyword typedef, for type definition.
And we're essentially saying, make string a synonym for char star.
That the means by which the stack created these training wheels known as
the string.
>> Now here's just a prototype for getchar.
We might have seen it before, but that's indeed what it does. getchar
takes no arguments, returns a char.
getdouble takes no arguments, returns a double.
getfloat takes no arguments, returns a float, and so forth.
getint is in here. getlonglong is in here.
And getstring is in here.
And that's it.
This purple line is another preprocessor directive because of the
hashtag at the beginning of it.
>> All right.
So now let me go into cs50.c.
And we won't talk too long on this.
But to give you a glimpse of what's been going on all this
time, let me go to--
let's do getchar.
So getchar is mostly comments.
But it looks like this.
So this is the actual function getchar that we've been
taking for granted exists.
And even though we haven't use this one that often, if ever, it's at least
relatively simple.
So it's worth taking a quick look at here.
>> So getchar has an infinite loop, deliberately so apparently.
It then calls-- and this is kind of a nice reuse of code we ourselves wrote.
It calls getstring.
Because what does it mean to get a char?
Well, you might as well try to get a whole line of text from the user and
then just look at one of those characters.
In line 60, here's a little bit of a sanity check.
If getstring returned null, let's not proceed.
Something went wrong.
>> Now this is somewhat annoying but conventional in C. char max probably
represents what just based on its name?
It's a constant.
It's like the numeric value of the biggest char you can represent with
one bite, which is probably the number 255, which is the biggest number you
represent eight bits, starting from zero.
So I've use this, in this function, when writing this code, only because
if something goes wrong in getchar but its purpose in life is to return a
char, you need to somehow be able to signal to the user that
something went wrong.
We can't return null.
It turns out that null is a pointer.
And again, getchar has to return a char.
>> So the convention, if something goes wrong, is you, the programmer, or in
this case, me with the library, I had a just decide arbitrarily, if
something goes wrong, I'm going to return the number 255, which is truly
means we cannot, the user cannot type the character represented by the
number 255 because we had a steal it as a so-called sentinel value to
represent a problem.
Now it turns out that the character 255 is not something you can type on
your keyboard, so it's no big deal.
The user doesn't notice that I've stolen this character.
But if you ever see in man pages on a computer system some reference to an
all caps constant like this that says, in cases of error this constant might
be returned, that's all some human did years ago was arbitrarily decided to
return this special value and call it a constant in case
something goes wrong.
>> Now the magic happens down here.
First, I'm declaring in line 67 two characters, C1 and C2.
And then in line 68, there's actually a line of code that's reminiscent of
our friend printf, given that it does have percent Cs in quotes.
But notice what's happening here. sscanf means string scan--
means scan a formatted string, ergo sscanf.
What does that mean?
It means you pass to sscanf a string.
And line is whatever the user types in.
You pass to sscanf a format string like this that tells scanf what are
you hoping the user has typed in.
You then pass-in the addresses of two chunks of memory, in this case,
because I have two placeholders.
So I'm going to give it the address of C1 and the address of C2.
>> And recall that you give a function the address of some variable, what's
the implication?
What can that function do as a result of giving it the address of a
variable, as opposed to the variable itself?
It can change it, right?
If you had someone a map to a physical address, they can go there and do
whatever they want at that address.
Same idea here.
If we pass to sscanf, the address of two chunks of memory, even these tiny
little chunks of memory, C1 and C2, but we tell it the address of them,
sscanf can change it.
>> So sscanf's purpose in life, if we read the man page, is to read what the
user typed in, hope for the user having typed in a character and maybe
another character, and whatever the user typed, the first character goes
here, the second character goes here.
Now, as an aside, this, and you would only know this from the documentation,
the fact that I put a blank space there just means that I don't care if
the user hits the Space bar a few times before he or she takes a
character, I'm going to ignore any white space.
So that, I know from the documentation.
>> The fact that there's a second %c followed by white space is actually
deliberate.
I want to be able to detect if the user screwed up or didn't cooperate.
So I'm hoping that the user only typed in one character, therefore I'm hoping
that sscanf is only going to return the value 1 because, again, if I read
the documentation, sscanf's purpose in life is to return to the number of
variables that were filled with user input.
>> I passed in two variables addresses, C1 and C2.
I'm hoping, though, that only one of them gets killed because if sscanf
returns 2, what's presumably the implication logically?
That the user didn't just give me one character like I told him or her.
They probably typed at least two characters.
So if I instead did not have the second %c, I just had one, which
frankly would be more intuitive approach, I think a first glance,
you're not going to be able to detect if the user has been giving you more
input than you actually wanted.
So this is an implicit form of error checking.
>> But notice what I do here.
Once I'm sure that the user gave me one character, I free the line, doing
the opposite of getstring, which in turn uses malloc, and then I return
C1, the character that I hoped the user provided and only provided.
So a quick glimpsed only, but any questions on getchar?
We'll come back to some of the others.
>> Well, let me go ahead and do this-- suppose now, just to motivate our
discussion in a week plus time, this is a file called structs.h.
And again, this is just a taste of something that lies ahead.
But notice that a lot of this is comments.
So let me highlight only the interesting part for now.
typedef--
there's that same keyword again.
typedef we use to declare string as a special data type.
You can use typedef to create brand new data types that didn't exist when
C was invented.
For instance, int comes with C. char comes with C. double comes with C. But
there's no notion of a student.
And yet it would be pretty useful to be able to write a program that stores
in a variable, a student's ID number, their name, and their house.
In other words, three pieces of data, like an int and a
string and another string.
>> With typedef, what's pretty powerful about this and the keyword sturct for
structure, you, the programmer in 2013, can actually define your own the
data types that didn't exist years ago but that suit your purposes.
And so here, in lines 13 through 19, we're declaring a new data type, like
an int, but calling it student.
And inside of this variable is going to be three things-- an int, a string,
and a string.
So you can think of what's really happened here, even though this is a
bit of a simplification for today, a student is essentially going
to look like this.
Its going to be a chunk of memory with an ID, a name
field, and a house field.
And we'll be able to use those chunks of memory and access them as follows.
>> If I go into struct0.c, here is a relatively long, but following a
pattern, of code that uses this new trick.
So first, let me draw your attention to the interesting parts up top.
Sharp defines students 3, declares a constant called students and assigns
it arbitrarily the number 3, just so I have three students using
this program for now.
Here comes Main.
And notice, how do I declare an array of students?
Well, I just use the same syntax.
The word student is obviously new.
But student, class, bracket students.
>> So unfortunately there's a lot of reuse of terms here.
This is just a number.
So this is like saying three.
Class is just what I want to call the variable.
I could call it students.
But class, this is not a class in an object oriented Java kind of way.
It's just a class of students.
And the data type of every element in that array is student.
So this is a little different and from saying something
like this, it's just--
I'm saying give me three students and call that array class.
>> All right.
Now here's a four loop.
This guy's familiar-- iterate from zero on up to three.
And here's the new piece of syntax.
The program's going to prompt me, the human, to give it a student
ID, which is an int.
And here's the syntax with which you can store something in the ID field at
location class bracket I. So this syntax is not new.
This just means give me the eighth student in the class.
But this symbol is new.
Up until now, we've cannot used dot, at least in code like this.
This means go to the struct known as a student and put something there.
Similarly, in this next line, 31, go ahead and put whatever the user types
for a name here and what they do for a house, the same thing, go ahead and
put it in .house.
>> So what does this program ultimately do?
You can see a little teaser there.
Let me go ahead and do make structs 0 dot slash struct 0, student's ID 1,
say David Mather, student ID 2.
Rob Kirkland, student ID 3.
Lauren Leverit--
and the only thing this program did, which is just completely arbitrary, is
I wanted to do something with this data, now that I've taught us how to
use structs, is I just had this extra loop here.
I iterate over the array of students.
I used our, perhaps now familiar friend, string compare, stircomp to
check is 8th student's house equal to Mather?
And if so, just print something arbitrarily like, yes, it is.
But again, just giving me opportunities to use and reuse and
reuse this new dot notation.
>> So who cares, right?
Coming up with a student program is somewhat arbitrary, but it turns out
that we can do useful things with this, for instance as follows.
This is a much more complicated struct in C. It's got a dozen or more fields,
somewhat cryptically named.
But if you've ever heard of a graphics file format called bitmap, BMP, it
turns out that the bitmap file format pretty much looks like that this.
It's a stupid little Smiley face.
It's a small image that I've zoomed in on pretty big so that I could see each
of the individual dots or pixels.
Now, it turns out we can represent a black dot with, say, the number 0.
And a white dot with the number 1.
>> So in other words, if you want to draw a Smiley face and save that image in a
computer, it suffices to store zeros and ones that look like this, where,
again, ones are white and zeros are black.
And together, if you effectively have a gird of ones and zeros, you have a
grid of pixels, and if you lay them out, you have a cute
little Smiley face.
Now, bitmap file format, BMP, is effectively that underneath the hood,
but with more pixels sot that you can actually represent colors.
>> But when you have more sophisticated file formats like BMP and JPEG and GIF
with which you might be familiar, those files on disk typically not only
have zeros and ones for the pixels, but they have some metadata as well--
meta in the sense that is not really data but it's useful to have.
So these fields here are implying, and we'll see this in more detail in P-set
5, that before the zeros and ones that represent the pixels in an image,
there's a bunch of metadata like the size of the image and the
width of the image.
And notice I'm plucking off some arbitrary things here--
width and height.
Bit count and some other things.
So there's some metadata in a file.
>> But by understanding how files are laid out in this way, you can actually
then manipulate images, recover images from disk, resize images.
But you can't necessarily enhance them.
I needed a photograph.
So I went back to RJ here, who you saw on the screen quite some time ago.
And if I open up Keynote here, this is what happens if you try to zoom in and
enhance RJ.
He's not getting any better really.
Now Keynote is kind of blurring it a little bit, just to gloss over the
fact that RJ does not get particularly enhanced when you zoom in.
And if do it this way, see the squares?
Yeah, you can definitely see the squares on a projector.
>> That's what you get when you enhance.
But in understanding how our RJ or the Smiley face is implemented will let us
actually write code that manipulates these things.
And I thought I'd end on this note, with 55 seconds of an enhance that's,
I dare, say rather misleading.
>> [VIDEO PLAYBACK]
>> -He's lying.
About what, I don't know.
>> -So what do we know?
>> -That at 9:15 Ray Santoya was at the ATM.
>> -So the question is what was he doing at 9:16?
>> -Shooting the nine millimeter at something.
Maybe he saw the sniper.
>> -Or was working with him.
>> -Wait.
Go back one.
>> -What do you see?
>> -Bring his face up, full screen.
>> -His glasses.
>> -There's a reflection.
>> -That's the Neuvitas baseball team.
That's their logo.
>> -And he's talking to whoever's wearing that jacket.
>> [END VIDEO PLAYBACK]
>> DAVID J. MALAN: This will be Problem Set 5.
We will see you next week.
>> MALE SPEAKER: At the next CS50.
>> [CRICKETS CHIRPING]
>> [MUSIC PLAYING]