Topic 10 - Bitwise Operations and the Live Heap

Outline:

• brief truth table review
• bit operations:
  • bitwise and, or, not, and xor (&, |, ~, ^)
  • thinking of basic data types as arrays of binary digits (bits)
  • intuition may be wrong looking in decimal
  • left and right shifting (<<, >>)
  • carry bits and the great bitbucket in the sky
• the heap is not the stack (per process version)
  • graphical representation, high and low values
  • linux: reading /proc/self/maps
  • sbrk for where the heap is and incremental moves
  • brief intro on brk for absolute locations
• exercise: tracking heap location with sbrk
  • “optimistic allocation” vs. pretouching / memset
  • tracing how much heap space is in use
  • optional: move the BYOA to the heap

Transcript:

Hello everybody, how are you doing?
so we are back and we have the
Enceladosaurus i think she's here
hi everyone yeah she's here all right
cool um
so uh we yep we missed last week but we
are back on now we're
pretty much getting to the end of c as
an additional language
the basic course that we outlined
um and it is uh it's been a fun
adventure hasn't it jess
it's yeah it said a lot i'm actually
surprised that we're already kind of at
the end
yeah well i mean we're gonna be probably
doing some project stuff but
i mean this is that that's basically c i
mean the whole the idea here was to get
through the c
language so um this original topic
was topic 10 uh and it was
i sorry i didn't update the web page but
um it basically this was kind of the
everything else
so as i told jess and i promised her in
a previous class
we'd done the good c and now it's time
for the bad see
so we've we've we've done the pure
true sea and oh and by the way hello
loaf bone
um so we uh yeah we're we're gonna get
just dirty with the language now so this
is we're gonna
focus mostly on bitwise operations i
think that they're all pretty dirty
so we're going to do a quick little
review of some of that stuff before we
throw jess in the deep end on that
um and then we're also going to
understand the rest of memory and the
way that you know programs execute
because
that we're there we're at the end to see
so we we could build a loader we could
build a kernel
right you know we want to build a whole
operating system chunk os
this this is this is the time so uh yeah
let's
let's kind of get into it so i just want
to show real fast before we
get going here's here's jess he just did
a epic stream with a
shave
shave head but um this is uh so just
what i was showing you here this is
kind of the topic that was here we're
going to split this part out so
um we'll we'll take the randomness stuff
and put that
and sort and we'll put that into a
separate section
i think that this stuff with the basic
um uh bit stuff is really
probably a lot harder um so i don't want
to try to junk up too much in
a single session uh so i'll get that
updated but uh
yeah let's um let's just dive in are you
ready jess
i am all right well let's
let's go for it so i'm going to throw on
the glove because we're going to need
some whiteboard
fun and we're going to review
what we know about our machine because
we know everything about the machine
maybe maybe not everything but like
feels like everything
so um no no no we know everything at
this point
this is oh it's all about libraries
right now team chunk
nice okay so um yeah we have two major
topics so we're going to talk about bits
and we're going to talk about the heap
so
uh bits bit do you remember it was a
portmanteau do you remember what was
short for
we had a little bit of trivia in that
class
it was a long time ago because i think
it was like our second session to be
honest
binary yep i'm guessing here yeah no
good
good guess is
it's actually the end of the word okay
uh
digit so
um that's a bit all right so it's a one
or a zero
and that typically corresponds to our
notion of true
and false and this is something we can
implement
in logic and there's i don't know how
much logic
i'm going to guess that like you don't
do a lot of bitwise logic
in python it just it's not really
unnatural for the language so i'll
at risk of being a little redundant here
i'm going to just very quick
version of logic so um this is two-state
logic
so this is classic two-state logic it's
also referred to as
boolean logic named after the dude who
invented it mr bull
and uh he he likes things to be true or
false
oh yeah that's totally true wait
seriously
that's actually wonder about the like
origins of that that's
that's that's a person's name
so the the actual boolean logic
and it's like pure form we are not doing
we're gonna do the
computer science like current day
version
like what you need to know for
programming version like i'm i'm not
gonna go too much into like all the kind
of craziness there but
there is um my discrete logic classes
from
this is totally your discrete yeah no
they will totally help
um but we're not going to do
aristotelian logic so i don't know how
much of that
that actually i feel good about yeah
that that that's like you've got your
you know for some for one for oh hey
what's up ccv
okay i got syllogisms down but not so
sure about the build
we're we're just not we're just throwing
that out we're we're 2500 years later
we have we have advanced we're we're
going to go crazy we're just going back
to two states aristotle had a whole
bunch of states but we're
we're not doing that we're not doing
aristotle we're doing we're doing our mr
bull
and mr bull said things are either true
or they're false
okay so if i have a single variable and
i name it p because you need to mind
your ps and later you're going to mind
your
q's but let's just say that this is
literally what this comes from so
if i have variable p here and it can be
either true
or it can be false all right and then i
have a variable q
and it can also be true or false but i'm
interested in all the combinations of
this so there's p
true and then there's q true there's p
true
and q false there's p false and q
true and there's p false and q false so
that would be the four combinations of
these right
yes all right so if i put that on a
table is this something you've seen
before sorry you could
okay so if i have this is true and this
is true
this is true and this is false this is
false this is true and this is false
that is false that's neat okay now we
can combine them
and we have three basic operations
do you remember what they are i don't
see this is
the reason i'm asking i don't know how
much like it's just going to be
like just super boring review and how
much of this is going to be kind of
fresh so
i three basic operations like
mathematically speaking
well for these two variables yeah
mathematically in the boolean world
there's only three things we could do to
them and you've heard them you've
definitely heard them in python so all
right at risk of being redundant
we have yeah yeah okay we have
p we have okay we have not p
we have we could do not q which is i
mean really the same thing but
um we could do p
and q i'm not going to write the formal
information for it because it's boring
so chat is saying by the way that
apparently i'm super quiet
oh generally speaking in person so oh
let me turn it no no that's because i
had that music blasting
let me know chat let me know is this
better when she talks
don't do that okay so
uh yeah like 25 of you okay so i think i
got that up
but goodbye let us know if that is not
good thank you chat
um okay so yeah so and and not
let's let's just let's let's or let's
clear our screen here let's let's just
let's let's mind our p's and q so we
have a p and we have a q
all right this is true true false false
this is
true false true false this is just the
short way i mean these are all the
combinations
yeah you're good um and then operations
being
and not and or right we could write the
formal math notation if we really want
to be boring but
um hey that actually might be more
familiar for me
no but you're fine i should if i'm gonna
write the formal notation i should write
it correctly this
usually you start with and which is that
one
and then um you know then there's or and
then there's
you know there's not which i guess in
formal would be kind of like that but
let's let's be computer-y about this and
not do that let's just write it out
because we're we're like that
so p and q p
or q
and not p we'll just do
not p actually i'll i'll use the tilde
version
so not p all right so not p is the
easiest give me the values
top to bottom uh false false true true
yeah piece of cake it's just whatever
the opposite of this
this first column is so that's all right
p
and q this is when both of them are true
so yep yep only one case
uh which is the top one and so then it's
the rest are false
all right and then or this is either one
of them
either so the first three are true and
then the last ones true true true
and false okay i don't know if you
covered xor
uh so i have looked at that because
it was in in this book of like preparing
for coding interviews and then i was
like i've never used this and i don't
even i've never even like
tweeted this at all so i kind of just
yeah it's not common
for like like high level languages it is
common for bit languages
so okay like it is a very useful
operation for example if you're reading
a nintendo controller you're going to
want this xor
but gotcha um it's like up in the higher
level
land it's a very odd operation
like it doesn't make much sense yeah i
read the wikipedia page
and i remember well it making sense when
i read it and then going
i never used this and it fell out of my
head it's just it's super sensical
it's literally it's one or the other but
not both
that's it yeah so it's exclusive or it's
just as opposed to you could call this
inclusive or which which includes both
and this exclusive or is just one or the
other but not both so that top line
where they're both true is going to be
false and the bottom line where they're
both false
it's gonna be false it's also gonna be
false here p is true and here q
is true so at least one of them is true
then xor is true
okay um now because we're in c world
these all have notations now
you can probably guess them but this is
and
this is ore this is not
sometimes it's just minus it depends
depends what kind of knot you want
and this is a carrot yep
okay so you'll probably use this the
least except if you're
reading a controller or something like
that and this this one is really common
and then you know this is
you know when you're assembling lists is
very common but
um from a practical standpoint you're
going to be using these two the most
often
and you are familiar with their doubled
parts like you know
like when you're doing a logical and you
know or you know a logical or like
that's more like you know like if
you know x is equal to four
and sky is blue
then you know do something um so
here we use this double notation this is
not a bitwise operation
this is this is a logical yeah that's
that's a lot that's and
they didn't invent this out of thin air
they just took the bitwise and operator
and they said all right well that's
uh well just two of those and you're
good to go
so um and same story with or so if you
just take one of these then
this this pipe operator and for anybody
in chat who doesn't know that is
the pipe is not a one if you were going
to draw them to scale
this might be like a one but this the
pipe operator is a vertical bar
some people call it but we call it pipe
because we're unix people and it's for
piping one thing to another
so anyway um
great so we did our review of our truth
table everything's piece of cake and
we're done with bitwise operators right
okay so how does this apply
to c you might ask because now we know
what the operator is
nice graphic low phone i appreciate
so how do you apply this to actual
values well
we're not dealing with single bits there
is no single bit type in
in classic c there there's some
newfangled stuff but we're not going to
get into that newfangled stuff
we're gonna we're gonna do classic c so
our smallest data type
what's our smallest regular data type
like least amount of memory kind of
small uh
character yep yeah character now we're
gonna be dealing since we're
not going to be interested in signs
we're going to be dealing with the
unsigned version of it
so this will be an unsigned care just
just because we don't want to we don't
want to allow any sort of
negative thing that'll that'll be a
little bit weird um
but we'll we'll we can get to that a
little bit later um so
how big is a unsigned care or a care it
doesn't matter
eight yeah it's eight bits
so great all of these operations apply
to eight bits at a time and that's how c
deals with them so
if i have a number like for example the
number
three in regular decimal
which in hexadecimal is
three okay and an octal
also three okay
i can't pull that out of my head but i
will trust your word you absolutely can
when it's less
when the number is less than whatever
the base is it's always just the number
so the one place you're going to run
into trouble
like okay so not in octal not in
hexadecimal not in decimal
but in binary what is three well turns
out three is greater than the maximum
value you have binary which is one
because
if you go past a one it overflows so the
number one in binary would be
one which is fine the number two in
binary would overflow because this
if i add one to this i can't put two
here
so i have to go to the next digit so it
becomes one o
and the number three in binary is going
to be one one one
one right because that's that's it um so
it's not too hard when you're down on
these like small numbers
to figure out okay so if i represent the
number three and i assign it to a care
so if i have my and i'm just going to
write the short version of this so this
is a ucare
t kind of thing which is just this thing
then and i call that x and i say you're
going to get the hexadecimal value 3
it doesn't really matter that i'm using
hex because it's exactly the same as
regular decimal anyway
then that actually in memory is eight
bits wide because you told me that
all right so that's these that's all our
chunks
and it just means that these last two
bits get activated
so this turns into 1 1 and all of these
are zeros
okay now if i have the number
four so if i take you
care t and i say y
is equal to the number four and again it
doesn't matter
what what i put it in it could be in
anything i'll just stay in hexadecimal
but
really meaningless down here um
so if i represent this number four
what's going to happen
binary wise the third bit is going to be
active
from the sorry from the right and then
the rest of them will be yeah exactly so
if i go back to my diagram
of that chunk of memory and i split that
up into eight
chunks which correspond to our bits then
i'm going to end up these two are both
zero and this one becomes a one
and all of these are not active as you
kind of said
okay so i have two variables that are
represented in memory
and these correspond to true here and
this is a true and a true and all these
are falses
i can write them all out but they're all
they're all false right there this
notion of zero and i go and i and these
two together
so if i do x and y
what am i gonna get you are going to get
uh all false yeah because
where is it all sorry all zeroes you're
gonna get zero yeah
yeah it's all false which is zeros and
that's because
none of them are both that's true right
so
it's going to go this one and this one
this one and this one this one and
oops not that it's going to go this one
and this one this one this one
and all of these none of them are going
to satisfy the and condition
so that's sort of our translation into c
land so this is going to end up being
all zeros which if i haven't all zeros
for binary
is the same as what number in decimal
all zeros is just zero yeah it's just
zero okay
sorry there was a second there i was
like just doubting myself and
yeah no i it's weird because while by
when you're dealing with bitwise
operations you're wanting to think in
binary because that's kind of where the
operation's happening
but when you kind of come back to the
real world of like decimal or hex or
whatever
it's a little weird and that's important
like that's okay to feel weird but you
have to understand that
this domain of binary is what matters
because
that's where the operation's happening
so i'm following you and i
i follow like if you were to tell me you
know do or well we're going to do
anything
it makes sense but i guess my question
would be
why would we need to do things on a bit
wise level i'm not getting into y at the
moment we're
getting into the rest of the language
and that means you got to know what bits
are
this is really important for something
called bit banging in c
which we're gonna that that's an
advanced topic but
um like let's worry about what you do
with it later
okay um for now let's just go over what
it is so
it's it's literally an implementation of
those truth tables that you saw
at the binary level so you have to just
treat this as
eight binary digits next to each other
well
yeah eight bits in a row so if i order
them what am i gonna get
um you are going to get three
ones so that would be uh the bottom
three ones right
yeah yeah so it'd be six
this is gonna be four
plus two plus one
seven seven yeah so it's gonna end up
popping out seven
um so this seems a little weird and this
seems a little weird if you're looking
at the numbers
because if you just looked at it as like
x is three and
y is four
if you or them there's seven
so it's like adding for that for that
one example for that
one example it is but if i make this two
then it's not adding so so yeah it's
dangerous to think about it
in this domain in non-bitterness when
you're whenever you're looking and this
is like a
really common mistake and coding problem
around c
is that you're looking at it and you're
thinking about it in decimal or hex but
actually it's not happening in that
domain it's happening in this domain
it's happening in the binary domain so
it's super important
to think about how many bits you got and
what's happening at the bit level
and this is really important for stuff
like
uh arduinos by the way
okay there's an awful lot of bit banging
down on on an arduino or any sort of
microcontroller
all right so high level bits make sense
yes okay now you can apply the same sort
of operation you could do an x
exclusive or with y actually which is
this is just a carrot
you know the kind of thing you get when
you do shift six um
so that's you know same kind of trick
just either or
no problem with these two numbers
because it's going to be the same thing
as or
b7 yeah it's going to be seven again um
and you can also knot this
right and if you knot this then you're
going to end up with
all of these bits flipped yes okay
so there you go there's your bitwise
operators
now those are your basic bitwise math
operators so they're they're in that
boolean
kind of sense now two more operators
we're going to worry about which is
if i have which are these
and you might have seen these in other
languages
i'm not sure um but they're
the shift operators so
this is again not something very natural
in python it's you know not
going to be common unless you're like
dealing with microcontrollers a lot
but it does happen and what is shifting
well it's literally just shifting the
bits over
so if i have a again unsigned
care which is eight bits as we know
and i have a pattern in there that was
really bad last
slash there's let me let me just mop
that up all right so if i have like
zero one zero zero one one
zero zero actually just to make that
interesting let me
let me put a one in the last digit okay
so if i have all these bits now this
represents some character so i can turn
this back into the decimal domain if i
want i don't feel like working
it out but uh
it's it's there so if i shift these over
one position to the left that's the
right that's my bad
so if i shift these one position to the
right
then what kind of pattern am i going to
get it's really obvious right
yeah just all the ones move one over
right yeah
i just now what comes in here
zero okay so this is sort of a argument
whether or not you're moving ones in or
not which
becomes a problem with negative numbers
for reasons we'll get to later but
from from like a from a hardware
perspective like off is sort of usually
the default right
so it would make a lot of sense
trust me those years of argument now
what happens to this last bit
it it just it goes to the great bit
bucket
the great bit on that's in the sky
we call that the great bit bucket in the
sky it just gets thrown now
it actually moves over to a special cpu
register but we're not doing assembly
language we're doing
we're doing c so again though like
and totally i know you said we'll talk
about what we're going to use this for
later
having worked with arduino and worked
with microcontrollers this makes
perfect sense the idea of shifting bits
one way or another
especially when thinking about like
gates and things like that totally makes
sense to me why you would need this
when you get to the level of like a
programming language though
then i'm kind of like well it's good to
know when i'm
building something but when i'm thinking
about the programming aspect of it i'm
really struggling with why i would ever
want to shift bits left or right
why would you i i don't know
that's a great reason we're you know
what i'm going to tell you that in a
minute but
okay for right now that is the
right shift operator and the way the
right shift operator works is i specify
a variable
and then i say i want to write shift and
then i specify
how far
sorry i'm reading chat um no no no no
don't worry about status registers we're
not that that's that secret place that i
told you about we're not doing assembly
the bit but is that the bitch button in
the sky and last miles is absolutely
correct don't worry this stuff
is important it's just oh i trust i
trust i have absolute faith that
it's important it's oh yeah don't worry
we're trying to like
make those connections let's let's worry
about how to do it for the moment all
right so
if i wanted to make this happen which i
just did in example two i would write
that as
let's say x gets this thing and then
this line would be
x gets right shifted by one bit
yes okay now it turns out we're sliding
digits
and binary is power of
what two yeah
right i mean versus like you know
dealing in decimal which is the base 10
or power of 10
kind of world and now when i shift in
decimal
what happens to a number if i take the
number 17
and i shift it shifting by powers of 10.
so it's an exponential
it's the same thing as in this case i'm
dividing by
10 if i move one place over it's
exponential if i do
several of them so this n would be that
exponent
so is an exponential even moving into
the decimal is exponential
yeah but i can think of it as just
sliding the digits
corresponds to division by 10 if i'm
going to the right and if i go to the
left
it's multiplying by 10. right okay it's
not the same thing's true
with binary except it's not 10 it's two
two so operations that are like multiple
we have operators for dividing
uh multipliers and dividers are super
expensive in silicon
so depending on what kind of machine
you're on now obviously any modern
computer
it's going to be super cheap but you
know that multipliers are not
super super fast like i mean it took a
long time to get to a single cycle like
multiply and it was tons of gates you
can
last miles i'm sure could write a book
on this
um so it turned out like back in the day
you'll see a lot of code that like
involved like if you were dividing by
two or multiplying by two you would
shift
because shifting is super fast in fact
the compiler will even
flip it to a shift because it knows
shifting is so fast
okay so that makes sense that makes a
lot of sense actually so this
this is important for like okay so we
can think of this our first case for
this is going to be
fast multiply and divide okay
now it only applies to if you're dealing
with power powers of two
so that's part of why you know we always
tend to pick blocks that are
powers of two right if i do divide by 10
24 i can do that
super fast because i could just ah it's
this many bits
it's 10 bits so i can just do a right
shift by 10 that's divided by 10 24.
so yes as last miles is saying
it is super super fast because it works
exactly it's just the same way why can
you multiply and divide by
10 when you're in decimal because that's
just the
pieces the structure of the length you
just yeah slide over the stuff
okay so that's pretty much
it so that's
bits okay um that's
basically all of the bitwise operators
now why i'm not really getting into why
too much but i can tell you the one case
that you're probably gonna hit most
in c is what are called flags
so in the case of flags you're usually
specifying something that's true or
false
for a bunch of values
okay um so like one of the one of the
cases where this comes up
all the time and i was originally going
to do it as our programming example
tonight but
then i realized it's a lot of octal and
i don't want to torture you yay
less torture is uh eunuch's permission
so i don't know if you've seen that dude
on um that that streams rwx
rob i think
i have very little time for watching
steam so usually it's
it's i'm very yeah i'm very limited in
terms of the streams i can watch
okay well this i i haven't spoken him i
haven't watched too much of his stream
either but i'm just gonna take a f
guess what this is this is probably
corresponds to unix permissions on a
file
um yeah which would be right
yeah right execute and execute
shmod okay now that actually corresponds
to bit pattern so back in octal land
when i had three bits
then this would be no permission then
read was actually the high bit so and
again i'm
i'm using motorola syntax here
um so this would be read this would be
right
and this would be execute now you'll
notice these only occupy one spot
right so you
uh multiple bits be true yeah i might do
something like i want
read or execute
which would give me what in c land
uh or is either one of them
is true so you could have a couple
answers there though well
right one answer for three digits three
bits rather
well so oh you mean like for the example
that you just wrote or
yeah yeah yeah yeah yeah read so if you
wanted to do read and execute
you could do this bit wise by doing read
or execute which would do what
what would you get you would need um
[Music]
one zero one yeah
and that's basically because you don't
have right mm-hmm
so rwx rob would be ours
read and execute not read or execute
though if you want both of them
because either that's what i'm saying
what happens if i end them
read or execute and you'll get one zero
either one zero zero or zero zero one
both of those could satisfy read or
execute
no not from a logic not from a bitwise
operation
so in a bit wise operation if i or these
two this one and this one
bit by bit i order them
right i take the one and the zero i get
a one
i take the zero and the zero and i get a
zero i take the zero and the one and i
get a one
i see what you're saying okay so
basically to get this like this is the
execute this is the right and this is
the read
then i need to use this or operator and
actually this is a
really common use in unix world of like
bitwise operations
now as we're talking about as i
mentioned earlier as last miles just
pointed out yes this is octal because
there's three of these
and this this is kind of a deck ism that
we all
get to long live deck rip deck
but um this this is kind of convenient
because
i can just use each of these bits as a
flag corresponding to whether or not
you have this permission okay and you'll
see this in c
you'll actually see like the the way of
actually specifying this
is exactly what we're writing out here
you know something like read or
now and by the way if i wanted to have
all three i would do read or
write or execute
and that would end up being one one one
right yep and if i dropped read it would
end up being zero one one
okay so we're just doing bitwise
operations there
so this is really bitwise operations are
really common for flags
and you'll still see them used to this
day in libraries it's still a common way
to do this i mean
i could just throw a whole bunch of
memory at it and use one variable
per permission but it would be very
wasteful of
in in silicon so and this was back in
an era where we didn't have a lot of
memory keep in mind
plus even if we did have a lot of memory
would you really want to burn all of it
on like permissions on a file like not
really like you want that to be compact
it's like where did the disc go well
it's all the permission stuff
okay so that's that's kind of a
practical case where we would use it
um if we wanted to read off these values
like say we wanted to test whether or
not so if i if i had some
variable x which corresponded to the
permissions for the file
and i wanted to tell whether or not reed
was
set how would i do that
i mean
so could you just do not
well i don't want to flip all the
permissions well
not like set that equal to oh i see what
you're saying okay so
like x is the permissions of the file so
i want to test where where's read
which bit is it it's the uh well it's
third from the
right yeah yeah third from the right
okay so um
how would i actually get that value
i mean could you just see if it's equal
to four
except that if there was right then
it wouldn't be four right um okay
right because if you're right that like
four is the number that it would be
like operated with
only yeah i assumed only read so you're
saying like how do you account for
right yeah this flags can be you know
whatever i mean in this case like you
could have any combination of these
so like you know four i mean i could
test all the combinations i could say
well if there's four plus the equivalent
all you would need to do is equal two or
greater than four
because if the other ones are are
switched on and that one's switched on
it's just going to be a higher number
okay well then
how's your algorithm going to apply to
testing for right
yeah so like it would work with read but
it definitely wouldn't work
yeah i mean so i could test every single
possible bit pattern that has a valid
right
would be one way to do it like i could
count all the multiples that have right
in them
or there's a simpler way using the
operators we just said
which operator only allows for
yeah which which operator only allows it
through if both are set
if both our set is and yes but we
wouldn't want that
oh we definitely do want that why
because
if i did this thing and and then i went
for the actual bit that i wanted
so let's say like for example i want to
have
one zero zero so i want to check for
read now again i'm assuming this is
octal but
um we're not actually going to code an
octal don't worry but
um so if i go and i and with this thing
the only time this is ever going to be
true is if this thing also
has that bit set
right if read is set on x and i end it
with this one well this 100 thing
then the only time that that's going to
evaluate
like if read is not set then it's going
to be zero right
right and if read is set it's going to
be
the equivalent of one in this digit
right and so
i can actually just and the thing with
the bit that i'm after
and then test whether or not it's zero
but wouldn't so if you if you did just
what you have there
and you had zero or
why do we only have four uh well so
there's two reasons one is because i'm
writing this as
octal octal numbers are always prefaced
with zero
okay so in that case like if we had zero
one one yeah last file and
the two you would get zero one
zero zero back you wouldn't get zero or
one
i don't see i don't understand how it
how you you said that if
if it was uh read permissions then we
would just get one
but i don't see how it's evaluating bit
wise so it'll evaluate
the first two and in my example
the first uh sorry starting from the
left would
be zero and then
the second one would be one and then
the third one would be zero the fourth
one would be zero so you would get zero
one zero
zero back you wouldn't get zero or one
yep right so you're not gonna get a
single zero or one back from that and
operation
or at least i don't understand no you're
only going to get one bit that's set
you're not gonna get a zero or a one as
the final result
it's the result's going to be whatever
the bit is that yeah okay all right
that's where i got
but that's why you can just test whether
or not it's zero because if it's zero
then
it the bit wasn't set and if it's not
zero then
the bit was set so no matter what
position this is in so if i was testing
like
in this case i was testing for read but
if i was testing for
right right so this this would
correspond to the number four
right so i could actually test the
result i could say like x
and 0.100 and i could say
is equal to four or not
yeah exactly okay so i could do that or
if i want to
not figure out what this is then i could
just say
this thing and that thing
is not equal to zero
but
but why but no
okay no i see what you're saying yeah
that makes sense yeah this this is just
an easier line to write than that
no no i see what you're saying yeah that
makes that makes sense yeah because now
it doesn't really matter what this
number is because like
if i'm i don't really care what this
number is i just care whether or not
yeah zero i really just following you
yeah like i i just
is there anything set or not you know
it's kind of like what i'm doing with
the
knot okay gotcha um so
we are gonna like skip this just because
this this is a little bit sticky with
the octal syntax i i don't
i don't really want to go down that path
so um we're going to we're going to
we're going to play around a little bit
there later but i mean at a high level
does that kind of make sense so i can
use
and to kind of peel off so here's your
first real use of and
it's like to peel off a flag so i want
to see whether this bit is set in a
given number
that's important like so say like you're
now back to the example that i was just
telling you with the nintendo controller
um a nintendo controller has
eight buttons
right it has four directions on the
d-pad
it has select start right so we have two
of those
and then we have two buttons here we
have an a to b
okay so there's eight of these total ah
funny
eight that's convenient
was that an accident i think not okay so
um what do we do with these eight values
well it would be really nice if they
were presented to us like eight at a
time
but how many wires would that require
well
you'd need at least eight corresponding
to each of these
you'd also need another wire for ground
and then you'd need another wire for
clocking
so you know your 10 wires in if you go
that way so that that's not
great so keep in mind the cost is like
directly proportional to how many lines
you're using
so so what's inside a nintendo
controller if you crack it open well
there's a shift register
and the shift register does kind of what
you think it's going to do with that
shift
word it basically takes
all of these values the shift register
is wired once
one to each of these buttons i actually
ripped one apart on stream
just to just to show people this but
it's really really simple it's just the
shift register in here
and it sends the thing out it has a data
line which is
where the value is going to show up it
has a clock line which is how you can
tell it when you're ready and has a
latch
and latch says freeze the state of the
controller
okay so how many buttons can be pressed
on a nintendo controller and this is a
trick question
at the same time i
my earliest nintendo was an n64 so i'm
not sure
okay well i mean just looking at there's
there's eight possible buttons
but they can't all be pressed at the
same time because have you ever
used a d-pad before yeah
i mean you can't press like up and down
at the same time
yeah so you can't press left and right
at the same time so you can only
like not all of these could be lit up at
exactly the same time but
um what i will get if i try reading this
thing in
is i'm gonna end up with a bunch of
values
eight of them in fact and i'm going to
get them one at a time
which is why it's called a shift
register because
this is basically the hardware version
of what we just did with the shift
operator
so it basically kind of like reads one
of these digits in and then it shifts it
over and it reads the next digit in and
then it shifts it over and then it reads
the next digit in
so when we decode this thing on the line
when we're actually reading the
the data line we're going to shift these
one at a time
and then we're going to build up a byte
so this is actually like
this is bit banging it's kind of
generically referred to as bit banging
so if we were going to read a nintendo
controller that's how we do it
and that's somehow that is fast
to just like shift everything over by
one and build up a bite and send that
out
that's fast it's certainly slower than
reading a bite at a time
i mean what would be faster would be i
read the whole thing in one swoop right
yeah except that would require 10 wires
which is directly related to cost and
nintendo cares about the cost
because it's not just the cost of the 10
wires right it's the cost of
the connector and then it's the cost of
reading it out of the board and it's the
cost of all the protection diodes and
you know all that
i mean there's a hardware cost
associated with every wire so you
like serial this is a basic case of
parallel to serial conversion so
parallel is like you have all of these
things at the same time
right you know so like all eight of
these bits could be
one or zero depending on you know what
the controller's state is
but serial is i'm going to read them one
after the other
so i'm going to read these one at a time
okay hey what's up sunny how you doing
hi sunny last miles what baffles me is
the amazing number of programs that walk
around we've never seen bits or basic
essentials that out
you know last miles i agree and that's
why we're doing something about it today
and that's why we're going to earn our
scotch
okay so we can read nintendo controllers
we feel
generally good about this at a high
level i mean it's
it's the same logic i learned in
philosophy it's just turned into numbers
so okay but we're not doing aristotelian
stuff we're doing i mean it's
if you were honestly if you looked at
like
the discrete math proofs that i did in
college it was
so many variables and symbols that it
looks like math which is why a lot of
people struggle with it
but honestly it's it's it's basically
the same ideas
i think what i have to remember is that
i am used to applying those ideas to
larger abstractions and to apply them
bit wise is really what this is just the
only distinction here is i need to
remember to
apply them at the level of a bit versus
applying them yes
at the level of an abstraction and
that's usually where people get tripped
up
that's like it's it's like it's super
obvious at the bit level and it's not at
all obvious when you're looking at like
the numbers so
don't look at the numbers okay
great i'm going to give us a nice big
check mark yay i gotta
get a gold star and we're gonna move on
all right so
let's talk about the heap all right so
okay
topic two this is we got to get through
all the rest of it so
okay we'll go bit banging a little bit
oh yep okay hold on sorry i got a
work message oh no we're good no no
you're fine i
i pushed some some changes right before
uh
dinner and oh there's always that
mechanical stuff where you're just like
like i'm pretty sure this is good and
then you get the message so you're like
but no all is always man you just went
like yolo
on it didn't you you just like throw
that code out there and
yell it out to pride a lot of testing
so i was very confident in it but
nonetheless you get that like
saw your and you're like so no we're all
good
everything went okay i'm i'm sorry that
you had that moment but
just just we're gonna we're gonna switch
it up here we're gonna we're gonna get
more
bluish that's kind of not a nice blue is
it um
let's let's go how's this green looking
that's a weird green ah
okay that's that's a nice green i like
that let's let's go heap
all right so what are we doing with the
heat the heap is green because it's
infinite right it just keeps on growing
that's that's not at all what happens
with you
but okay now do you remember what i told
you very
briefly about the heap and then i just
like quickly didn't talk about it at all
and then we just remember it's not the
stack
yeah it's not the stack that's great it
is not
all i remember okay because it sounds
like super but it's not this
it sounds like the stack it acts like
the stack it walks like the stack it
talks like the stack
it is not the stack and it there's one
major difference from the stack you
remember what that was
i have a i have like a feeling but it's
not something that i could entirely put
into words i remember so
i represented
[Music]
okay sorry go ahead tell me your
feelings
i remember that even though this is a
wrong metaphor
that when you described it the first
thing i thought of was like
ram versus yeah uh hard drive okay and
so
that the heap reminded me more of ram
and the stack reminding me more of hard
drive
and i okay i don't think you can write
things into memory in the heat but the
heap was like temporary storage or
something
okay yeah i don't really remember that's
wrong that's kind of that's that's on me
i have i have not explained it so we
just really quickly talked about it so
the stack
let's just talk about the stack for a
moment the stack is where we're usually
talking about stack frames and
because we're the kind of people we are
we draw the stack as growing in which
direction do you remember that
okay the stack stacks of coins grow up
no we go we grow down yeah we go down
no i remember it being like there was
some fancy pants word for it that people
were using in chat
yeah there's all sorts of fancy pants
we're going to try to avoid fancy pants
words but i'm sure
chat is going to use them um so in our
world we're going to
talk about the stack growing down all
right the heap is not
the right is not the stack yes and it's
also not the chunk
it's not the stat actually the chunk
should be in the heap
we put the chunks it should be in the
heat yeah
we actually did chunk it onto the heap
when we
mall locked the chunk as opposed to not
mallocking it so
um okay so we talked about the stack
growing down and i quickly told you that
the heap grows in the opposite direction
of the stack
okay so the heap typically now again
these are not hard rules different
architectures
actually me i'm so sorry but like oh we
are totally going to talk about that but
you okay
because i i thought it was like a
convention for how to refer to it but if
they're opposites i feel like there's
got to be like a hardware
component to this or is it just like
there are dimensions it depends on the
hardware right
right yeah that again depends on the
hardware
that's exact it depends which
conventions you adopt so typical
conventions they're growing into each
other
and typically like so in a given piece
of process memory
you're going to have the you know
process memory being like a process
is a word for program that's running
so we can just call this a running
program
um so when i'm talking about process
memory then
i'm using the stack when i'm doing
function calls typically like you know
i'm putting parameters onto the stack
so this is like when i call a function
they go onto the stack
when i get out of the function they come
off the stack and that's that's that's
the stack is typically growing down from
whatever the top
memory address is of the process so if
the process
is built to run in say like
like 100 is the top of the memory and 0
is the bottom of the memory we're just
going to pretend this is a micro kernel
so then the stack is going to start at
like memory address 100 so this will be
one memory address 100 so if i have a
pointer to this it's going to be
100 and if i take the next four bytes of
memory say i go and i get myself an
integer
here then i'm going to burn myself four
bytes of memory these are all single
byte chunks these are eight bits wide
so um then eight eight
eight there goes my four bytes then my
stack is going to be here
and if i allocate another number then
it's going to be 888
and my stack is going to be here i'm
running out of memory
well at least on my diagram because it
wasn't really drawn to scale but
you know let's let's let's clean that up
a little bit all right so
um that's how the stack is growing and
then when my function returns
it gives that memory back because you
know that that memory is only local to
that function
right okay um so that's typically what's
happening in a stack frame
now the heap i told you is going the
other way
so it's starting down it doesn't start
at the bottom of memory because
typically this is where the program
itself is
this is called the text um so
this is like the text would be like the
the text in the if a program was a book
then the text would be the the
instructions to follow to read the book
right that would be the words in the
book
so this is this is referred to as it was
a very classic
world back then when we used to refer to
like program binary as text
okay it was a long time ago so
um anyway uh so we called that the text
and then there's some other stuff that's
that's usually sitting around here and i
don't want to talk about that too much
there's things like um
the data segment and you know there's
initialized data
sometimes there's this uninitialized
data sometimes
you could have as many segments as you
want depending on your linker but we're
not we're not going to get this where i
got a
segmentation flow oh yeah yeah because
all of these are segments right you know
it's like okay i'm giving you this part
that's the text okay i'm giving you
a segmentation file just say false with
your segment yeah it's when you
reach over a segment so
like the most common place where it
happens is up here like like say you go
and you access this memory that's up
here
that's not your memory this is like soup
nazi like no
no soup for you okay that's segmentation
fault right you just you cross the
boundary there you know that that's it
you're out and it kills your program so
actually
again see you're lucky if it crashes
back in the day used to just right into
somebody else's memory which was
even worse because their program would
crash
okay so this stack just kind of kept
going down the heap did exactly the
opposite thing and it would it would
point up and there was a notion of like
where it was at a given moment
on the stack we called that the stack
pointer on the heap we can call it the
heat pointer if we want
it has other names but um
so and that just kind of tells you where
that heap is going to come from and it
sort of just grows up
now in between these two is actually
where we
decided to allocate a whole bunch of
dynamic libraries
in between the heap and the stack yeah
we said nothing's ever going to grow
into there but if they do we'll just let
them
i mean the idea kind of being like crash
your own program and don't take down the
whole system
you know like so the idea being like
make it like not that this worked
perfectly but the idea was that if you
kept taking memory
you would sort of eat your own memory
like at some point your stack would
overflow
but you overflow into yourself you would
overflow into say you're here so it's
like protection
yeah so like protection may be for the
system but not really protection for you
yeah but the idea being that like you
wanted your
like own program to crash
like you know from the operating system
perspective like you know the programmer
was like no i want all the memory it's
mine
so as last miles is pointing out it was
a real
thing so actually my hatred of emacs
dates back to that era so that's
yeah that's that's because emacs
for for people that know what things
like the heap and the stack and bits are
then
emacs actually stands for eventually
malloc's
all core space so that's
that's because he emacs was like a beast
and it would just take all of the memory
on the system so
anyone who was running emacs was being
very rude to everyone else that was on
the machine
so that's that's kind of where my issues
with emacs stem from they have nothing
to do with the actual modern editor but
okay um so we briefly mentioned that
there's this dynamic
libraries thing and then we briefly
mentioned that there's this stack well
actually we've talked about the stack in
a lot more detail
and now we've mentioned that there's
this heap thing typically when you're
mall locking stuff
and this is not every implementation the
standard doesn't say anything about it
but
back in the day this was very common
malloc would take from the heap
so this is why i told you we could take
our chunk allocator
and we could just malloc a chunk it
would it would come from the heat
we didn't actually have to mall lock it
at all we could take it directly from
the heap ourselves if we wanted to
and that's what we're going to do today
using the s break
command so this is about adjusting where
these break
levels are this is this is a kernel
level function typically
and it says like i want to adjust where
things are going to be
so this is um
this is kind of the key insight into
that world this is typically our
boundary
now we're not going to write a full
loader we're not going to have to do
deal with like pulling our text off disk
in order to be able to run our program
we're not going to deal with
initializing our memory we're not going
to deal with initializing the stack but
we could do all those things if we
wanted to and c and in fact in
microcontroller land
typically we do yes last miles
really but we're not really going to get
deep into s-break
she she did write her own version of
malloc by the way last week
you missed it yeah that was that was
chonk alloc you got to be part of team
we had we have team so i'm just going to
throw that up here this is for team
challenge
it is for team chong team chunk knows
where it's at
okay so chunky
chunk really wants to live here in the
heat
but uh chunk started life off over here
in the stack and that's all right
because
we're gonna deal with that so um great
now one last thing and this is where
we're going to start programming today
have you ever seen slash proc
sorry what yeah uh there's a
so this is really kind of about unix
internals but there is a directory so
slash is always kind of the root on
on it sort of like c colon windows i i'm
more familiar with unix than i am okay
windows
so in linux actually just about every
unix there's this thing called proc
which is about processes and it's about
tracking like which processes are
running and if you look in there
you'll always see a whole bunch of
numbers like you know there's like 117
and there's one and there's one two four
eight and then
you know whatever the process identifier
is which corresponds to a program that's
running is gonna be in there
so if you look on a modern computer
you're gonna see a lot of stuff
in slash proc i don't know if you have a
linux box
up and running but if you if you just
peek into slash proc you'll see a whole
ton of things
now how do you know what your own
process id is well there's there's
something called get pid and you can
actually ask the system
for it so that's one way to go but you
don't actually need to worry about that
because there's this handy little thing
which is called slash proc slash
self and guess what that refers to
the process idea id of the currently
running
yeah this just becomes whatever my pit
is yep
all right and then in here there's
something called maps
and this is what we're going to start
off programming we're going to go look
in this file because
this tells you what is mapped where in
memory
so memory addresses oh yeah
well let's go find out so that's
actually our exploration so
um i think we're going to come off the
whiteboard and we're going to get
actually we're not going to be doing me
coding we're going to be doing
you coding okay this is
uh yeah let's let's go take a look now
proc
keep in mind this is normal unix file
system stuff
so we can just open it like normal files
and this is just a text file
so you can imagine this is sort of like
maps.text in a
in a in a if this was a windows world
so um but we're not even going to write
that because it's blasphemy on the unix
system so
um yeah go ahead why don't you open that
file up
and show it to us on output
okay
what directory or i guess i can just use
an absolute path um
it's uh we're not using pho open
i didn't teach you to use open never
never use open i don't even know what
open it is
that's the old school that predates like
the stdio
every time we open we
yeah let's be good c programmers well
try
okay so it's just a text file so i can
read lines
do i need like can i use my normal
buffer size for this
or yeah well let's find out you're the
programmer
time to put all those skills to use
we're in like the last class here
well second to last for the basic chords
ah what did i tell you about that
always use a specifier
thank you it is new line terminated so
you're not going to need to add the new
line
assuming that your thousands big enough
but
we'll find out okay that's one line
okay how many lines are in there
how do you get the size of a file can i
just use size of
uh no i'm guessing
stuff never works the way i want it to
no we
did actually see this operator when we
were doing file parsing when you didn't
know the size of the file and that just
like now you don't know the size of the
file so
at the end of a file using standard
stuff there's a
there's like a a terminating bite or
something yeah right
yep there's an end of file mark and you
know
you don't need to worry about how that
is spelled out in the system because
we're just gonna use a function that
knows how to find it
okay which is feof
okay i'm vague memory it's been a few
weeks since we used that one
well we haven't parsed yeah we haven't
done much parsing now we're not gonna
parse we're just gonna dump out we're
not don't worry
um so if i go and i
if so how do i know when i'm at the end
of the file i say as long as i'm not at
the end of the file
so as long as implies what kind of loop
while yep so while i'm not
at the end of the file oh wow
you you only get one allocation of the
memory you know that
don't don't don't do that there let's
i'll start you off here um
so wow
chap by the way you're killing me let's
not talk about the scotch yet i'm um
yes i'm craving and um what trying to
get through the lesson
oh no it only takes one i'll tell you
right now it takes one argument it takes
whatever the file is
okay and that'll just get so what does
it return i'm sorry
uh it returns a value which if it's
you you can just nod it okay so while
not
yeah while i'm not at the end of the
file
it reads like english except it's vof
end of file oh yeah
all right okay but you've been in
python too long because our wiles need
to have these
parentheses yep and this does not have a
terminator
yeah okay and then we have to close that
yep so that's our basic loop right
right do i it's indented yeah it should
be ending makes me happy
okay um now this will do one extra read
for reasons that i'm not that interested
in so
don't worry about it just go ahead and
pop it out all right
let's clear the output oh we got a lot
of stuff
didn't we
and we got a lot of big numbers didn't
we okay this is real memory
harris by the way is in shock at your
hair i think
who is oh harry studios hi you missed
stream last night
yeah it was it was there um so i'm gonna
just show you
i'm gonna walk you through real fast so
uh stuff
so this is web input is the name of your
program i always compile it to be web
input at the moment
um so and uh this
basically is telling us kind of where
our memory is going to get started so
it looks like memory addresses but is
that like yeah these are memory
addresses
it looks like memory address like blank
through
another one and then the permissions and
then
yep something else some number i don't i
don't know
and then a time and then another number
yep we're not going to worry too much
about that format
what we are going to worry about is the
first thing on the line and the last
thing on the line so
this corresponds to some sort of address
and this corresponds to what's there
process id yep now if we were fancy with
our parsing we could actually just snip
it
but let's i told you you don't have to
do parsing tonight
that'll be your homework um
and so what we do is we're getting a
range and then we're going to see like
what it's assigned to so
that's that's kind of like what's
happening um at a high level now this is
all of this memory is sort of mapped to
whatever our executable is
and then what's this
uh what i'm sorry hold on i'm waiting on
stream i oh i can't see your highlights
hold on
um what do you heap it says heap it says
heap that's where the heap is
that's actually why we're looking here
okay because we want to see how memory
is organized so
this is actually the heap this is where
the heap is at the moment
and we're going to find that out using
the s break command in a second but
that's that's the actual
that's it now the next thing you'll see
i know the hair is fun
it's all right it's all right this is
super complicated but
um no i'm following you uh so what
happens
after the heap well i told you what you
were gonna find there you're gonna find
a whole bunch of
libraries so these are your dynamic
libraries
that are in use so we're using lib c is
mapped here so this is actually where
your function calls are going for things
like str copy and
feof um so and libsy is here and
libsy is here and libsy is
over here too and that's fun um so
there's only and then there's ld which
is the dynamic loader itself
so that's actually what's responsible
for doing all this work for you behind
the scenes
and then we see some
other junk so there's some stuff that's
not specified there's some more
libraries
now depending on your program there
could be a lot of libraries or not
right depends how many you have linked
in so if we added curl
which funny that we were looking at that
earlier
then we should see it here now um
what's the next thing we see that i've
now highlighted for you if you can see
it
uh give me one second i'm catching up a
stack okay and we're finding the stack
lower down except if we're looking at
these addresses
they're higher up right remember we
started that okay i'm not going to be
i'll start
probably uh okay well i mean just
looking at it here a little
we'll copy some of that over but this is
basically kind of where the stack is
and this is kind of where let me pull
out the heap
this is where the heap is so um
if i just compare these two numbers i
can quickly see that this starts with a
five and that starts with a seven so
this one's bigger than that one so
in the notion that i'm drawing the stack
with the stack is growing down
it's going down from high level of
memory and the heap is growing
up from a low level of memory and it's
getting bigger so that's actually where
they are
so if i want to stack overflow this i
need to do a lot of work
there's a lot of numbers between these
two wait hold on
look at this for a second no but
hold on
processing please um
and then the heap and the heap
okay that makes sense what is what is
what is v var
don't worry about it oh okay
there's also vdso there's there's
there's a whole bunch of other stuff
that you get
i'm just curious because it was the same
notation that it's been using for like
stack
and heap and then it had these other
terms that we've never discussed
it's important um it's more important if
you want to get into operating systems
it's not so important for c uh because
this is
more operating system dependent than it
is like dsos
um and sys calls these are actually
where some of the lower level operations
are happening that
this depends what version of linux
you're running this depends if you're
even on linux at all or you know
so this this stuff i'm not going to get
into because it's not really kind of c
related
the stack stuff is if you want to build
an operating system this stuff is
more interesting we need choco
s yeah if you want to build chocolate
pledged
to make chocolate and then we could
start worrying about those things but
um anyway um so
there it is there's your stack there's
your heap that's actually where it's
hiding now if i wanted to read these
permissions we know how to
know how to deal with bits now i don't
want to torture you with the
example i had so the lightest example i
could come up with
which i think is okay sorry
fairly safe if i may
um so anyway that that's our memory
organization so if you're ever wondering
this is actually where you can look you
can look at this self
this proc self maps and you can actually
see what it the allocation is
now this changes keep in mind every time
i execute the program because we don't
know where the operating system is going
to throw it in ram
right it doesn't always throw it into
the same place a running program stays
more or less in the same place but you
know if i every time i run this thing
i'm starting a new program so it may or
may not land in the same location in
fact it's likely it won't
so that brings us to our last
well for this part that brings us to our
last command which
i sent to a man page for before yes
and that is s that is
s break
okay so what does s break do well
it changes the break where that heap
boundary is
so that okay
basically if i tell it it takes one
argument which is a number
and that's like how much more memory you
want the heap to grow
which
does that
so there's like this no man's land
that's between the stack and the heap
where you set a lot of bees
it should stay in no man's land because
if it ever becomes a man's land then
our program is going to crash so
does changing the break point
for the heap does that change
the the size of the stack
no okay good all right so that it's
the no man's land that's shrinking it's
on the heap side of the no man's land
so if it ever changed the stack that
meant you grow you could i need a map
okay no um
we draw it right i know i know i'm i'm
trying to visualize it um
okay actually here i will give you that
so let's let's just quickly go back to
the whiteboard so
um this is when i was looking at this
thing
i had sorry i'm just throwing the glove
on here i had the stack
was growing down
uh-huh and the heap was growing up
now there was some other stuff down here
which we're not going to worry about
but because we just learned about it and
then we knew that somewhere kind of in
here
is those dynamic libraries and we just
saw that
they're all there and they're happy um
so this is actually kind of where you're
calling
libsy in particular was here so when you
were calling
like feof and you were calling
f open and all that stuff that was
actually being resolved to this area
so that's where those things that's
where that functionality is living at
the time that you're calling it
um but this however much of the heap
is quote live
this is so in use which yes
in use um is kind of where the break
point
is for the heap so if this is kind of
where the heat
the end of the heap is this is some
location in memory
now if i grow this because i want to
have more memory like say for the chunk
allocator
like say i want to have like two megs
then
this is gonna have to grow and in order
to grow it we're gonna have to ask the
system
hey it'd be really swell if you gave me
two megs which would be two
times ten twenty four times 1024
because this is bytes and this is
kilobytes well this is bytes to
kilobytes and this is kilobytes to
megabytes and this is
i want two of them so um
so this amount is how much i want you to
go up
okay i want you to grow that break point
this was this was traditionally referred
to as the break
um so that's what s break does
and when it returns it tells you where
it returns a void pointer which
corresponds to where the heat now ends
so you can sort of tell like did the
allocation work or not because if if the
heat didn't change by the right amount
then you know you didn't get that memory
that was a little fast at the end um so
just looking at the heap side of this
drawing
so i start my heap here
i grow it by say i don't know
16 bites
so this address in memory should be
whatever this used to be
plus 16 right and then
now that's where heap is but
so
memory addresses i guess when we were
talking about pointers right and we used
this metaphor of addresses to houses
yep and we talked about things like
metaphors
but we also talked about things like
memory padding which made
actually a lot of sense don't worry
about padding we're not getting so
so no but my question is
why bother having all of those memory
addresses if
for the most part especially on modern
day systems so this might be like a
modern day question but like
you for the most part won't be concerned
about an
overflow of 8 bytes 16 bytes if most of
your memory is written in chunks that
are
larger right and so when you draw these
levels these are larger than
like 16 bytes right so why would it not
say let's say we're dealing with a very
i don't know small system and so each of
our each of our little chunks that you
are drawing
horizontal lines for is eight bytes
would it not be that it is
two memory addresses above that not 16.
yes
okay i wasn't i wasn't drawing the scale
but yes you are you're absolutely right
if these are eight
big because of our memory organization
then yes um
now i can tell you that like on our
modern system these are usually
much bigger yeah they're usually 64. 64.
yeah
no no that's fine it was just but yes
you're right i'm not trying to scale
anymore because now we're starting to
talk about big numbers
fine totally fine it's it's more for my
own like verification that i'm
understanding
i should have warned about that that i
had sorry that i dropped scale but
um so totally fine okay now if i need 16
more
bites then i'm just going to say all
right system i want you to grow again
by another 16. so
now the heap is going to be here right
you're not
in some way you're here right
can you draw the stack though sure i
don't want to draw it to scale
no no that's fine that's why let's
pretend it's a very very tiny stack or
something or we're in some
m.c escher stack land where stuff is
just i'll just i'll use the dots in
between to indicate
a lot of space here um so
the stack pointer is going to be
pointing to wherever the bottom of the
stack is
right okay so that's important
when we get to nintendo's so because
there's not much stack space
by the way it's really easy to blow out
your stack
okay okay you really do have about 200
bytes
that's it seriously yep yep
yep and if you write into that whole 200
bytes you're probably writing into the
zero page so you're probably calling
functions and not even realizing it but
um we're not we're not going to worry
about the topic to the um
scratch so i don't know i read this
article
that was obviously a popular like pop
science article so it wasn't really
going into the details
about how on the first moon landing
the code was somehow like sewn into
yeah like okay and i just like i i
literally
just my brain was like no okay like what
so i would like
you oh expert of all things code related
to explain
what the heck is going on with that
because it sounded really freaking cool
and then sorry this reminded me when you
were talking about these very small
machines and it reminded me of
how limited the early spacecraft were in
terms of
memory yep and you know one thing led to
another and i i've been meaning to ask
you about every
every bit there mattered i could i could
tell you one that's really cool but also
too i'm sorry
sewing wait what yeah so well it's
we we don't talk a lot about physical
processes all right all right let's save
that for
um yeah sorry that was i i figured that
would be a good scotch
i'm i'm i'm itching for the bourbon
before you get this
space so yes it is super cool and
actually i was just reading about their
multiplier that they
so if we want to move the heap then we
do it by
so if we want to move the stack this is
typically a register
so there's actually a register that's
usually referred to as the stack pointer
so i can actually just do math on the on
that register directly the heap
usually does not have a register it may
or may not have a register it depends on
what kind of system you're on
so this is typically an os call which is
why we're going to be using
s-break and s-break basically returns
where you are right now
and you pass it how much so this is
basically
like how far do you want to move the
break point
of like you know this being the break
point
okay so what it is encroaching upon
though is that neutral no man's
neutral zone it's a neutral zone right
absolutely a lot of a lot of these
people were trekkies by the way
so um okay so
this this we specify how much and it
returns
where so using this we can smoke out
where the heap
currently is because we can just say s
break zero
so if we say like move the heap by
zero bytes then it'll tell us where we
are
so let's start there okay
okay so ready
code
um now i'm just gonna quick
you're gonna need this for a little bit
so i'm just going to leave it here but
let's
let's just comment it out to
keep it out of the output so
i just told you that s break works by
specifying how much
and it returns a void pointer which is
where yes
yeah rope core memory nice love fun
um okay
all right
and not to press but the faster you do
this the faster we get bourbon
oh no i'm sorry
[Laughter]
oh and thanks for the follow sentinel i
missed that earlier okay
so our goal here
is to increase
our heap memory
because well let's find out let's start
off by
where is the heap so we could parse
that maps thing yeah but i just told you
another way we can get it from s break
so let's use s break
okay and i'm just going to help you a
little bit because i'm thirsty
um uh
you're going to need this in order to be
able to call us frank
that's good that's good to know okay but
so the s break
we need to know how much well and
yeah tell it nothing don't move at all
oh right because it's that's how much to
move it not how much talent okay yep yep
we're good
so moving it is allocated
oh so first this is just placeholder
delete this um returns where so a memory
address so this is going to be a number
technically right
so i'm going to need a pointer to
address in memory which is a void
pointer because
it makes no implication about the
semantics
so that's the where
uh
okay heap what's that rogue space doing
there
what rogue space oh yeah sorry that was
[Music]
um
excuse me
the heat begins in a world where the
heat begins
ah sad face is it because it needs um
[Music]
how much we want s break to move it by
so i can't just leave it empty so is
there
tell it zero
[Laughter]
it's okay and
this is because it's int and it's yeah
yeah so it's
telling you by the way at the bottom
it's saying no you know what it's memory
address you really want to use this
percent p so go ahead and use percent
it's very nice these days it's very
polite and it tells you
oh look at that nice hex yay
and we can see that that happens at
roughly the same
sort of magnitude as the earlier run
you'll notice it's not exactly the same
as the earlier run
no okay but if i run the program again
oh look it's different yeah it's the
same
general area but yeah it's a bit
different if i'll look at that it's
somewhere else it's somewhere else
somewhere all right we don't know where
the os is going to put our program
in fact our program should not know
where it's going to end up in memory
okay we sort of want our program to work
anywhere that it happens to land in
memory which is why we use standards
like c
and we try to do the good c but we can
do the bad c if we want
um and this tells us where we are
but it's relative to that execution so
you can't compare these heat pointers
across executions
okay that makes sense like it's only
that's the heat pointer for the program
that just ran
and then that program terminates so when
you run it again it's going to be
somewhere else
yeah so all right now let's go
ask for 16 bytes of memory
well let's remember where we started too
so um
so you want can we
let's see um
can i override it or do you want another
no i want another variable
okay
nice
okay what
it's the same
linux lies to us all the time
i mean we can ask for a lot right we can
we can say like all right you know i
want that two megs that i told you about
and it does not give the same
i told you before that linux uses
optimistic
memory allocation right
so does it not give it to us unless we
use it
yeah that's that's called touching the
page so
we actually have to start using the
memory to get it to
gotcha so we need to put something or we
need to have our program use that much
memory
right yeah so i'm writing
copying pasting writing notes um last
miles is asking for another 10 24 so
we'll just sneak a little bit
more yeah we're still running to the
same sort of issue here
so why are we doing what harry's studio
don't look at without
don't look at what he don't don't read
what last mile said don't don't read
what he said because that's that's he's
totally giving you the answer
oh i was reading harry studios i wasn't
reading last month okay so what are we
doing
uh we're how are we going to use that
memory
um
[Music]
let's think about this
accidentally saw my last milestone all
right all right well then let's just
let's
these last miles is right that's what we
want to do
okay i mean i wouldn't have the answer
anyway my guess would have been
think of something that would take up
that much room in like well if you
didn't
yeah if you didn't have memsat then you
could just loop through and
set it to zero right yeah okay so
um you're all right last miles don't
worry it
um so uh yeah uh
yeah this isn't a test if last miles
knows how to
touch the memory okay um so this is by
the way
something that java does all the time
you can you can ask it to do it's called
pre-touching
so you can basically say i want to
guarantee that i have that memory like
so i want before
you kind of do anything with it like
force the os
to sort of like definitely give us that
memory
because right now it like may or may not
give us that memory so um
mem set is basically a way to set one
value
for an entire range of memory so it's
it's sort of like
str copy well except it's not copying
um it's it's closer to like you know b0
but we're not using those crazy berkeley
kids
in programming style um so basically it
it just i'm gonna i'll give you the
function parameters for it so
memset is this is all you're really
going to need
which is this thing
so this basically takes
where you want to start it takes what
you want to put in each location
and it takes how how much
n bytes of memory pointed by s with
constant bytes c
okay so yeah c is the constant so it's
going to put this
value in every location
it's going to put this value in every
one of i think it was
n size t so
this is how many this is what to put
there so
just put it zero and this is
where okay so
and then the size i'm guessing in bites
now we shouldn't have those magic
numbers i blame uh the teacher here for
that
but
oh my lord sorry my mic is wait
i think that's a little uh that's a
little too much there so
that's uh oh plus yeah i'm sorry i was
trying to copy
and all right so all right so if we
set it and then we look at it again
because now we need to know where it is
after that it should change wait wait
wait
where did you check the s break before
or after the mem set
after but we need to so we need to do it
again
with s break zero to see where we ended
up
i see so let's just call this
we know that this is a safe safe
safe save heap start
you're gonna need to start because
you're gonna need it in a moment
yes harris so in a previous
uh session she actually created her own
version of malloc
i feel like there's no better way to
understand an alligator than to write
one
okay yeah let's take a look
ha ha change now
here's why how much memory did you get
two times now what did you ask for how
much did you get from the system
you're not guaranteed to get all that
memory
six two 122 000.
wait no no no no no no it's first of all
it's gonna be billions because it's
megabytes but
second of all um i'm just subtracting
the two addresses
so they're in hex um
but why don't we i don't know you have a
computer
let do the math
that's why we saved our start address
okay um
[Music]
can i just subtract them oh harris
definitely not we're
c programming now so
i probably have to make this this is
going to be some kind of
integer
uh can i just subtract them yeah
that sounds great uh
you can subtract memory address right
you don't need to
just you can okay i'm gonna i'm gonna
help you with this one
because that's do i have to cast them
yeah that's basically right that's
basically right but what i want to do
i'm gonna just get rid of this variable
you want me to just do it right there
put it out oh okay that's fine
let's just yeah let's just get that
number
mhm
sure it'll fit
you'll never have more than two gigs of
memory right
so many programs brooke
all right 2.2 million
thank you best break now it totally
lied to us because until we did our mem
set
it was not giving us that memory before
it was giving us exactly the same
addresses so
now i don't want to go screwing around
with it but
let's that there's voodoo
under the hood is all you need to know
like okay you don't know what the os
is actually going to do until you use
the memory so pre-touching is a pretty
good pattern if you want to be
guaranteed that memory
so for example if you're running your
chunk allocator and you want to make
sure that trunk got the memory that
chunk was promised
and that you're not dealing with a bug
that's related to the system and you
won't be able to report things then
you'd better do the s break and you'd
better touch the memory to make sure
that you actually got it
gotcha okay does that all make sense
yes great now do a binary operation all
no i'm just kidding that's