Topic 9 - BYOA: Build Your Own Allocator

Outline:

• malloc and free as the defined interface
• building a stack based / null allocator
  • use a single chunk of global memory
  • doesn’t disappear with function calls
  • avoiding fragmentation, never reallocate / free
    • easy to just keep moving the head pointer forward
    • free is a non-operation outside of stat bookkeeping
    • no one-size-fits-all allocator
• keeping track of available and used memory
  • optional: tracking report of unfreed allocations
• can dynamically allocate the chunk up front (simple heap version)
• issues with flushing output; crash could happen before output
  • fflush guarantees the output “made it”
  • stdout is actually a file, can fflush it to guarantee delivery
  • printf(...); is the same as fprintf(stdout, ...);

Transcript:

hello everybody how are you doing sorry
about the little delay a little bit of
fun we were just having with the uh the
editor but
uh we do have jess here jess you're here
hi everyone hey jess is here okay um
so we're going to be we're we're back
for c we're going to do c
as an additional language this is topic
9. i did not have a chance to update the
syllabus but
on the website but i did update the
syllabus and my notes so
i'm going to work off the notes we have
basically one topic tonight
uh jess seems to think c is easy and
she's just been i say that she's been
flying through the lessons and going you
know this stuff this memory management
that's a piece
of cake i do this stuff all day so i
think
i think to get a real appreciation for
uh what's going on with memory
management
we're going to be doing some fun tasks
that we discussed last week so
the subject for today is really kind of
a split
between what we had in topic 8 in the
previous
syllabus so last week we really focused
on binary i o
we did a little bit with pointers so
this week we're gonna go pointer
happy because it's time to get to just
kept asking
how do i dynamically allocate memory and
she wanted to use that
that bracket notation and just leave it
brackets and say oh well the c compiler
work and that works at declaration time
but it does not work after declaration
time so
in order to do that we had a very brief
introduction to a function
that do you remember what it was jess
that yes that's exactly it the dynamic
memory allocator and i said
and one of the questions i asked was
well how do you like implement this
because at some point someone had to
implement
malloc so for tonight
we are going to implement our own malloc
i told you it'd be fun
uh this is gonna be we're gonna go for a
very simple allocator the kind of simple
allocator that i mentioned
uh last week so this is here we are we
have jeff's on the screen we're in topic
we're in topic nine and
strophe says gross how do i flag not
safe for work
yes there's only one topic on the board
bring your own allocator so we're gonna
we're gonna make our own allocator we
are going to
understand dynamic memory in ways we
have never understood dynamic memory
before so
i would this this part is really
the focus we're gonna go for the
simplest possible allocator
which is the one that i briefly
mentioned last week which is the
uh stack and by the way that 20 that i
rolled that was a real 20. that
the camera was on you all saw it so that
i really rolled that 20. so
i feel like that 20 this this 20 here
is going to help jess tonight because
because
malloc is oh boy waited
if it was weighted it was weighted at
the factory i i got this die straight
okay
so um this will be fun so we're going to
do
a stack based allocator and so let's
let's get into our
coding screen here alright we're going
to
talk a little bit about i'm not going to
just throw her straight into the deep
end and go all right go implement
malloc we're going to we're going to
help a little bit right and chat's going
to be helpful because strophium
really wants this to be to work
all right so we're going to do oh wait
we're not we're not doing topic eight
we're doing topic nine oh man why do i
have this super
crappy brush so i just did an os upgrade
and
my brushes are all over the place this
this stuff is
tell me i lost my yeah that's my
streaming pen
all right i don't know i don't know why
this
is going to be something is that still
readable or is it just impossible it's a
little hard i mean i think i can make it
out but i'd worry about some folks on
stream
yeah you know what let's let's figure
out because they
i just upgraded and of course whenever
you upgrade
your operating system wonderful things
happen so
i had some nice streaming brushes that
just don't want to i don't want to
rename the group i want to fix the brush
all right come on
all right edit brush settings let's
sorry everybody
let's let's take a moment now and
and deal with it okay so brush radius
we'll just bump the radius up and that
should be good
all right hopefully yeah okay that's a
little bit better
i don't know where my normal brush went
i'll go debug it later
all right so let's let's do that yeah
all right now we're crazy brush
all right so um great we have brushes we
have painting
we have topic nine so this is c
as an additional language
and we are going to be building our own
allocator
so let's do it
now i don't know why there's such
tremendous lag
on this pen all right i'll worry about
that later
it looks nice it looks nice to me okay
well if it looks good to you that's
we're good that's the most important
thing so we really only have one thing
to do we have to build an allocator
and how do we build an allocator well
the interface was already defined
so we're going to be implementing word
for word
the same interface that we have on
matlock and
actually let me put that over here
because what is the actual interface for
matlock when you call malloc
it gives you back your favorite new data
type
pointer yes okay yes it was a total
guess
because we were talking about those
earlier and when we're allocating memory
what do we have to tell it
how much yeah how much all right so
that's a
that's a size thing so we're going to go
with a size t and it has something like
how much
all right and don't worry about the size
t because this is
this used to be an int but you know you
can
it's gonna be aligned for the platform
and it's a standard thing but anyway
we use size t it's just basically a
number but it's gonna be a positive
number because
you know you don't have negative sizes
okay and
we had a matching call when we were done
with the memory what do we do to it
um free yeah and what do we have to give
free
free takes the size it doesn't take a
size it takes
um it takes a what a pointer yeah
exactly so it knows like what to free
yeah we have to tell it what to free and
so it that's going to be passed in as a
void pointer to be nice and generic
and this is this is really free what
okay
um and it doesn't return anything that
we're really concerned with so
this is our this is our interface it's
well defined
we have to malloc has to allocate memory
and chop it up and hand it back to the
program
dynamically and free has to you know
deal with cleaning it up so this dishes
it out this cleans it up
okay any questions on the interface
i don't think so it's time tested it's
mother approved it's been around for
ages okay so actually malloc is
absolutely not mother approved i think
i think if my mother was a programmer
she would not be happy about the state
of affairs okay so
um great well how can we build this
and by the way keep in mind you're going
to be coding this so we're going to want
to build this as simple as possible
so first of all what do we need to do
like like at a high level what are we
doing i mean we're taking in
like um you know keep in mind we're
taking in a size
and we're returning a chunk of memory
so in order to be able to dish out
memory what do we need
we need memory memory
yeah no totally not a trick question um
so we need a nice chunk of memory all
right and this is gonna be our
heap of memory as it were this is
now i'm gonna put that in quotes because
it's not actually on the heap it's gonna
be on the stack tonight but
we're gonna we're gonna get to the
difference of that in a little bit we're
just gonna refer to this because
in the original sense of what the heat
meant this was just a heap of memory
so um great now what we need to do is as
we're matlocking we're asking for
different sizes so say the first person
comes along and asks for malloc
of i don't know eight bytes okay so we
need to go and say
well this was the start right we need to
know where we started
this is the end when we get to here
we are out of memory
oh no so this is this is bad
um we we don't want to get here because
bad things are going to happen so
we want to sort of stay but you know we
don't really control that when we're
writing the allocator we have to just
deal with whatever
you know the user requests from c so
all right we allocate we our first call
is we matlock eight so we're gonna take
this little chunk here we're gonna say
this is eight bytes
wide and we're gonna give you that back
we need to give back a pointer to the
start of it so
here you go and then the next dude comes
along and says i want a malloc
four and so we're going to say fine i
got your four
take this and advance it by four so
it'll be half the size
and here you go you're good to go that's
your chunk of memory
and the next one comes along and says i
want a malloc
something that's the size of
a planet because we learned about that
the other day
and we had a nice structure planet and
this
ended up being 14 bytes after we packed
it so the compiler knows that so we
don't have to worry about it
and it's basically going to say yeah
here we're just going to advance this 14
we're going to take this chunk
and we're going to give it back to you
so there you go there's your 14. so
bookkeeping wise what do i have to kind
of keep in mind
i have to watch where i am
right it's really important to kind of
know like what the furthest chunk is
now when free comes along and starts
having to deal with this situation so we
take this thing and we want to free it
and then we take this thing and we want
to free it and we take this thing we
want to free it
what do we have to do we have to say
that this is no longer in use
right so this this memory is now
available
to be reallocated if we want and
that's on the first free call so that's
the free call that corresponds to this
matlock
and then on the next one when we when we
take this thing now we don't know what
order they're going to be deallocated
and they might not be deallocated in the
same order that they were allocated in
right this one might get removed first
and then well let's let's assume the
eight did and then the second one was
this
you know 14 byte thing so then this one
was left back but
i still have this memory here in the
middle so if somebody comes along
asking for this whole chunk i can't take
it from here
because that's not contiguous i only
have this
this part and this part so we're not
going to worry about this case of
reallocating memory like i said that's a
good allocator we're not going to try to
build a good allocator because it has to
deal with this problem of
you know how do i keep my memory from
getting fragmented
you know like you know there's this
piece and then there's this part but we
gave that back because the person called
free and
then there's this piece so how do we
prevent this situation from happening
well that's pretty advanced topic so
we're not going to try to do that
tonight so it's sufficient for you to
just
always return memory and don't worry
about running out because when you run
out all you have to do is just crash
okay technically malloc doesn't crash
malloc returns null
so if there's no more memory left you
have to return null
okay okay so quite a crash
right that's not a crash at all but it
usually ends up being a crash because
who checks the return types
well it's common practice not to so
crashing is probably safer like like i
said you know you're lucky if it crashes
so
um we could you could build your version
of it to be non-conforming and always
crash whenever you run out of memory
so um so free really has to do a lot of
work normally but for your
implementation
free is gonna be really easy all three
is gonna have to do is just say
well we're done with this but we're not
gonna give it back
so you're just always gonna keep
allocating forward
makes sense okay i think so all right
well so in order to do this
we need a chunk of memory like we said
so we're going to call that
chunk all right
actually each of those was a chunk so we
can we can just refer to this as the
heat but
let's not overload the word heap too
much so let's let's say that this is our
our pool um so
you're going to allocate memory out of
the pool uh this is this is
commonly called a pool actually but um
so
your pool starts somewhere and then you
have to kind of
keep an eye on how far you've allocated
and you're gonna have to keep updating
like okay we're
right now we're here then we're here
then we're here then we're here because
it was a big allocation
and so on and so forth so we just have
to keep updating where like kind of the
the next allocation is going to come
from right
okay and when free comes back we don't
really have to worry about now a normal
memory allocator would try to reuse the
memory
but we're not going to reuse it we're
going to say it's burned so
once once the memory is freed it's just
burned forever
so what we're essentially doing here
then is we're
rebuilding malloc that's kind of what it
sounds like yeah
all right yeah we're trying to build a
simple version of malloc
okay to get kind of a sense of what
malloc does how memory allocation works
and
it's not some magical like second
language that comes in like
malloc is usually implemented in c
okay all right so um
we're doing our design so we know that
we need to know
like where the where the head is um
you know so like what i guess i guess we
could refer to this as the head
so this is kind of like where where the
next allocation is going to come from
you know so this is where it is this is
where it is this is sort of like the
whole
chunk so we can we can refer to that as
the whole pool
and we need to know where it ends right
so this is
this is the end and after that we need
to we need to return
null after that because bad things or we
could crash or whatever
okay so malloc we cut a piece
and we give it back right free we're
just going to burn it
so you good to implement i think so
or do you have any other design
questions before we get in there
um
so i guess this this is probably a very
silly question but like i understand why
for a simple version of it that we're
just going to pretend that free
sort of you know burns it right but like
why let's say in your example so you
have this pool
and let's say that um for the sake of
argument it's like subdivided into like
five evenly spaced or even not evenly
spaced
things and four of them the first four
are
like you can make them however big and
the first four are occupied or they're
being used
and then we free the third one
and there's something that i'd like to
store that takes up
two of the the chunks why does it have
to be contiguous like why wouldn't we
just
uh that's the guarantee from matlock
why by definition that's the definition
of the malloc interface is that you get
back a contiguous chunk of memory
sure but why why does that mean why is
that the definition like wouldn't it
how do i know more memory if you could
say take that thing i want to store
and store it across those two chunks of
memory
so like you want to hand back like this
one and this one
well how would i how do i know how how
does malloc know how you're going to use
the memory
but why does it need to be contiguous
because let's say that i
set myself a character array and i
wanted it to be
you know it's a buffer and i want to get
like
from your allocation i want to say i
want a malloc 10
24 all right let's let's
write correctly so let's say that we
want to get a k
what would happen if the middle of this
thing was not contiguous
later on at some point i'm gonna be
doing like buff of
511 and that's going to be
a byte that i assigned something to when
i str copied into it
and then when i get buff 512
how would this work i would have to add
a whole way that
the way the way that we've talked about
things being stored in memory
especially with pad pardon me um
we don't need things to be contiguous
if they're like padded out we don't have
to worry about things being split over
where we think think about the
programmer who's going to use this
interface
like they would need to know how to deal
with things being split
i guess i don't understand why because
this this what i just wrote doesn't work
i i from
buffer 511 is basically taking buff
and it's doing a pointer offset because
this thing's actually a pointer
and it's adding the size of care times
511.
it's actually doing a point or offset to
get that memory location so
to get this memory location it would be
buff whatever the address is
plus 512 except it's not because now
we're not guaranteed
it to be you have like relative
addresses oh well that would be a whole
other language you'd have to build like
trace every future access i mean how
would you do that in c i mean you would
have to trace
whenever the user was accessing the
memory you gave out and you would have
to
patch it on the fly to say oh that's not
actually here it's over here
but especially with the use of something
like pointers i feel like that kind of
idea of relative addresses is almost
already built in
okay let's if you feel strongly about
this let's just talk about it at the
discussion time because i can tell you
that that's almost an entirely separate
language you're creating
to handle that so we'll just we'll put a
pin
why contiguous and we'll just we'll
discuss that at the break because you're
gonna need
basically the full clock to implement
malloc with the contiguous sense so
okay i was just curious like why it had
to be contiguous that's all
okay it's at the moment it's by
definition the way the language works
so that's for the moment all you need to
know but like we can get into why they
chose to do it that way at the
at the break well at the discussion all
right
so that question aside any other
questions before you implement
um i don't think so okay uh
let's let's go do it then
of course it wants to get rid of your
window that's nice
oh stream oh man what's it doing
okay something bad happened to obs
oh no obs oh
yes why why do you do these things obs
all right you can already start typing
and i'll just fix your
window whenever i can figure that out
i mean i'm a little bit i understand
conceptually what we want to do but
given that the way that we've learned to
take chunks of memory and set them aside
as malloc
obviously we don't want to use malloc
because we're trying to build it
so yeah that's the way that we've
learned to like engage with memory
really is through malloc and so
yeah so we gotta build it we gotta we
gotta know how it works right
right but we haven't really learned any
other way to
access memory right
uh well you're that's literally what
you're building right now right
i mean we're basically using arrays to
build our version of matlock
okay skype is really being a dude
okay i i re-added the window so i'll
fix the title bar in a moment
okay so you know what the inter start
with writing the interface like
what what does it have to you know for
what right write your malloc
function let's call it uh e malloc for
enceladosaurus matlock um yeah i was
thinking about that and i was trying to
think of what it would return right
because technically it returns
it would make sense for it to return a
pointer to the
start of the chunk of memory that we
want it to set aside
right yes so but that's not necessarily
a void pointer
it's a pointer to it's just a pointer
it's a pointer to
some memory address so i wasn't sure
what that okay
this part is actually super easy because
you don't get to choose the interface
because
we're going to build exactly the
interface that malloc uses from the
library so
i'll okay this isn't like a design
decision we have
we're going to make something that's
compatible with the existing malloc
implementation so when we're done we
should be able to use
th and so i just copied um like yeah
okay you could you could use it
all right and you know you can you can
build free as well
now free is gonna be kind of a no-op
it's not really gonna do much
but you know we have to provide the if
we
have an allocator we have to have a d
allocator
okay so
malloc sounds like a harry potter
villain yeah totally
whereas if you make amalgam and uses
every single vitamin for start to finish
all the time you get very yeah okay
surfing we're going to get into that in
the discussion smoke yeah allocate
continuous block a different undress
yeah okay that's true too hi poppy
yes obs is just i don't know why it just
did that all right
so anyway let's
let's build so emalloc you know what the
interface is
okay so
let's see
[Music]
i'll even i guess like come down here
and call your function for you
i want 10 bites
so
like the way that i'm thinking of it
kind of even in pseudo code right is
that
we have to start at
the very beginning like like the most
easy is all of our pool of
of memory is free so we can start at the
beginning how do we define that pool of
memory yeah yeah
we gotta start with the pool right so
without let's start with a pool that's
2k but how do we do that without using
malloc
uh yeah i mean how do you refer to a
byte of memory what data type do you
have that's one byte
characters yeah right all right so let's
use unsigned care because we don't
really want to
like and this is common uh unsigned care
is usually used to refer to a byte
because it adds no semantics it's just
basically like kind of the raw bite
okay so we have an unsigned care and
instead of pool we're going to call it
wait wait wait wait
wait wait we need an unsigned care
that's a sign care
oh i don't remember how to do unsigned
care
uh it's not not a remember thing it's
it's uh you just do it
okay except 2k in the computer sense is
2048 so it's power's a two right
you can learn the bad habits later from
so i'm sorry what are you okay that's 2k
to a computer okay
okay now allocating this thing
inside e malloc
puts it on the stack it's a local
variable to e malloc
which is going to be a problem because
when we return it it's going to destroy
the stack for the function when it
unwinds the stack
so we can't put it there
at least not using using only the things
that i've shown you so far okay
where can we put it that it'll live
beyond the life of the function
well so this is where we kind of get
into the trouble of we haven't really
talked about
how to build functions that can be
called from other programs before
because if it's in main then it can only
be called when this
program's run but if we need it to be
something
that will be called whenever malloc is
run
i'm not sure it feels like it should be
like outside of all of that like right
like just here yep
that's yeah it should be in global space
okay okay so chunk
this is our pool you might want to use
the normal terms because they're they're
going to show up in the documentation
just
okay you can use chunk if you want but
you might be confused later when you
actually start reading about memory
allocators
um okay so then hey akshay how's it
going
yeah give it bites all right we'll get
into that at the
discussion strophium
all right so
she's gotta learn the term pool don't
you think yeah i know she's
it's some will it will it help you if we
make it chunk
no it's just like when i'm writing
things at least just being silly and
stuff like that i feel like just adds
kind of like a humor element but
i'm just worried that later on this is
because this is going to be hard but
all right let's let's go with junk so
okay so we have a chunk we have a chunk
of memory
which is what we're going to divvy out
so that's our right that's our whole
pool and what we need to do is we need
to kind of keep track of what
with it so we need to keep track of
what's been used
yes what's already kind of been
allocated right yeah so where we are
exactly so i think we need like a i
think we need one more global variable
to be honest which is like
our place sure and now by the way to do
a memory allocator you're going to need
to use some memory
to do your own bookkeeping right so like
memory allocators aren't free right they
need a little bit of memory to do
management of memory
so i think it would make sense to
just kind of like have have this is
basically our index
right and so i think if we just kind of
have like
to start out with right okay
and so that is that is a variable
that we can then update when
whenever part of me malloc is calls we
do like index plus size
okay index equals index plus size right
so that'll change sort of what the index
is
yep okay all right so except do you want
this to be able to be
negative
uh no so i guess we can just do like an
unsigned yep
yeah it should be a sign type you and
well you can use the classic type so
unsigned int is fun
yep okay so we don't allow it to go
negative it's it's this thing's positive
yeah and that makes sense um okay so
javascript is for fun oh yeah josh like
the
c for seriousness is like sort of lolled
a little bit
anyone who thinks javascript is fun
though no i mean i'm not i'm not into
like you know
um pooping on on various like
uh coding languages but javascript i'm
not sure if i would describe that as
for fun oh chat by the way how were her
levels compared to mine are they like
kind of like
roughly even because we forgot to ask
yeah we forgot to ask like it's
i had to quickly set them up so if she's
a little quiet let me know or if i'm
quiet or whatever she's a little low
okay i'll turn you up a little bit
all right so when she says something you
can tell us more tests
can you hear me better now
thank you fran a little bit low
still low
okay better better all right okay okay
um all right
so
let's think about this so
the memory the piece of memory
so the like piece we're gonna need to
say
hold on let me think about this okay um
so we did unsigned character right so
this is going to be
a piece of memory right and this is
going to be
let me think about this hold on so
i don't even know if i can index like
this but like index
write the start to index plus
size
wait a minute hold on one second brenner
let's
let's not crap on people with
programming languages let's
let's just let it go there's there's
good people in javascript there's bad
people in javascript yeah i mean
i actually know a few javascript
programmers who are beautiful wonderful
people they're not all
i just i'm very bad at javascript and so
so they can do things that i cannot i by
the way i dislike javascript too but i
like i don't
dislike all javascript people i mean
it's yeah strophium
strophium kind of has has exactly my
approach which is this it's something
that i'm less interested yeah yeah
compared to other programming languages
honestly after doing a bit of front-end
work i
they they earn their pay seriously i
have so much respect
for for like ui ux designers front end
developers like
yeah no i'll stay in my happy back end
land
for sure so okay explain what's going on
here with your slice that doesn't exist
in c
so essentially what i'm thinking
is it's kind of like
um when you're integrating from like x
to x
plus i right except from here
we need to allocate a chunk of memory so
we're slicing
from the index which is our changing
start point
right from start to start plus whatever
the
size is yes and we know that our the
index of our array thankfully because we
picked characters is actually
like part of me 0 to 10 would be 10
bytes
because because we're guaranteed
contiguous memory but we'll get back to
that later but
the so the indices that i need
are going to be essentially the
end of the chunk minus the start of the
chunk
is going to be the size our indices work
that way thankfully like like we said
because we said it that way
so we need to index we need to take a
piece of
oh wait this doesn't make sense hold on
hold on i got you i figured this out
that doesn't make sense because we
actually need this to be the size
yeah yes and then it's going to
equal
yeah from there to there yeah and so you
said i can't do that
fine but that's sort of the approach
that i'm thinking yeah
yeah um i mean that
pseudo code wise that kind of makes
sense
okay so how do we actually do that right
i mean that's pretty much what we want
to do is
like return the memory from there to
there so
well so i've got a question actually i
think this might work
because given what we were talking about
arrays with pointers so
okay let me talk out loud and see if i
can figure that out so well first of all
what's the return type you need to
actually return
the return type that i need to actually
return what do you mean
what is void yeah it's not just a void
it's a void
void pointer yes so let's declare one of
those because that's what we're gonna
have to get back
okay so
uh i don't know what to call it
um
i mean brenner you're definitely
entitled to your opinion we could we
could also get into a bit of
language fun i'll pin that as a topic
javascript language okay keep going
sorry
so okay i do what strophium says by the
way i always name my return result
but yeah you're calling thing things
good i like thing
so we need to basically fill out a thing
right and so here's what i'm thinking
is that okay i have to think out loud
when i code so it's really funny
actually when i'm programming at home
because i'll just be like talking to
myself totally fine but so
all right so the piece of memory that
we've assigned right so this is an array
and actually
no i don't want this i don't want this
this is a bad idea so i'm actually going
to
do that for now because i don't think
that's actually a good idea um
because i think what we need to do is we
already have the size
and while this would work
if we uh had already declared the size
we need the pointer to it and so
what we actually need is like a little
well an array right okay so
ah i'm like there hold on so this this
this yes
yes actually yes and the thing is is
that
a void pointer though um
but i want to return just a real pointer
not a void
sure the interface is void oh no
you don't get to change my lock it's
been around longer than you were born
old things aren't necessarily good no
but we are building something that's
binary compatible with the old interface
so we have to do it that way
so
all right so in this case then
we're gonna cast it i don't even know if
that's gonna work but that's like the
only thing i feel like i know how to do
right now so
this piece of memory right we've decided
we're going to i feel like
i know that i need to declare it but
when i declare it like this i feel like
that takes memory
or does it take memory it it does you
don't get to declare it
i don't want to declare it i want to
just say that
it is equal to something so can i can i
do that when i declare it
so if you declare it there where is that
i don't want to do that yeah you can't
because it'll be in the stack frame of
exactly malloc so by the time you return
it's gone
but is there a way to like so
can i say that this is like this is
equal to
um this is this is the problem right is
i want to do that again like index plus
size thing
right and i know that doesn't work yep
so so in the existing malloc how do you
know where the end of the memory chunk
how does that how does it tell you what
do you mean how does it tell me it
doesn't really tell me it just gives
a pointer to the start yep but we have
to know that that
no but within malloc it has to know that
that memory is available that's true
so that's your own bookkeeping but
that's not related to what you have to
return you don't return a slice
you're returning just the start of it
right okay so that's true all right so
hold on
so really what we need to do here is all
right so this was wrong too hold on
so that's our return and this is going
to be
and so what we actually want to do is
we all we need to do actually is check
since we're burning the memory and the
memory is going to be contiguous all we
need to do is
check that check that the
memory address at
index plus size is free
mm-hmm so so there's like a like i don't
know if c has like an assert but there
needs to be something like an essay it
does but you don't get to use it that's
a
that's a debug thing so let's let's skip
assert for the moment
your math is absolutely right so how do
we know where the end of chunk is
like how big is chunk
2048 bytes yes and we have an operator
that'll tell us how big chunk is
in the event that you change that number
size of right
so if we wanted to build another global
just i don't mind that we're going to
burn a few variables to make this
problem easy i want to make this problem
as easy as possible we can always build
a more efficient version later
so how can we assign
the size of chunk like so we can say
like total memory or something like can
we make like an
another size t which is the total amount
of bytes available
because that's actually so that would be
in my mind
at least because we have a couple of
assumptions right our assumptions being
and at least just the the physicist and
me bear with me so we're like
we're assuming that memory is going to
be
allocated contiguously and we're
assuming that freed memory cannot be
retrieved
that's just that's for our
implementation yeah yeah the first one
is actually a rule of malloc
the second one is an assumption we're
just that's a simplifying assumption
and that's fine these are the
assumptions and so because of these
assumptions
we don't need a third variable that is
how much memory is left because
our index is our proxy for that okay
because that would just be
2048 minus index and that's how much
memory is left
let's do it for cleanliness because you
know rather than
putting 2048s all through your code we
could just have a single 2048 and then
we could say the size of chunk
is how big it is right so
what i'm what i'm not sure i follow you
i'm sorry um
this is kind of where i'm leading so
let's say that we
uh and actually you're using unsigned in
so i'll use unsigned dudes
well actually this is uh
this is um total memory
and this is going to be the size of
chunk now this isn't a big deal
for c because this is a
this is known at compile time right
so the compiler can put that in like we
we can run this thing and we should be
okay right
so okay built-in
oh is that already something so
i'll just call this i wait
oh i mean normally so it's a built-in
functions normally
unsigned is no no don't use i because
it's like everywhere like
if you put that well we'll use index but
um no it's telling it's saying that
there's a built-in function called index
oh and it doesn't want to see that's why
yeah let's not use i because i gets used
in almost every function as a counter
so you'd have a global one and then a
local one that's that's bad voodoo
so we don't want to override the same
thing let's let's call it like chunk
index
you know just to just so that we don't
trip over you know okay
okay so we're back to compiling clean
okay
so this line works line eight
because the size of chunk is known at
compile time
right it's 2048. now the nice thing
about using this is that i don't have to
put another 20 40. i mean i could just
put this in here as like
this is also 2048. and i could just have
2048s littered all through my code but
the problem is that
that's not really good programming
because then i'd have to replace all of
those whenever i want to allocate more
memory okay
okay so we know where the end is we know
where we currently are is chunk index so
all right back to your email lock what
do we got to do
so
we need to check that so the thing is is
that you're using this like
size t type that like
i haven't really we haven't really used
that apart from just like it being in
some
some of the um documentation we've
looked at
and so actually i've hold on i've got an
idea i don't know if this is gonna work
i'm gonna take
uh i'm gonna mess around a little bit
hold on so i think
it would be interesting to say that we
have
um
that is um
see this is why like i kind of like the
idea of having
because we can you've already declared
size
where it's in the email oh yeah that's
in there um
so um
and i want eye size to
be equal to
like cast on to the size oh yeah i mean
you could do that but i could tell you
that size t is just an integer it's an
unsized integer
okay so that's the thing is i haven't
really used that it's just data type
before
so it's specifically it's a standards
data type it's not used in general
programming
us except it's defined exactly as the s
the type that sizeof returns
so it's okay that's why it's used in
standards instead of but it's a number
like i could add
yeah because int is one of those like we
don't exactly know what size int is
depending on the platform like so
size t is kind of like they don't need
to be exactly the same size
right size t has to be exactly the size
that size of returns
it doesn't so it could be or it could
not be but that's the reason why we're
using si
they're basically both numbers they're
both integers but
so i have a question so if
i want to print something
that is at a certain memory address if
there's nothing there will it return
null
if there's nothing at the memory address
c doesn't make any definition about
what's at a memory address you didn't
initialize
what do you mean so if you didn't
explicitly write something to a memory
address it's undefined what it's going
to return
could return no it could return not null
it could return anything we don't know
what it'll return
well let's let's use the unsigned
character array that we have
if there is nothing at
array index five and i say print chunk
five
yep what what what will it print
what do you mean by nothing was
something written to there before or not
that's no no so i'm asking this because
i need this as a check
so let's say that nothing was written
there before then you have no idea
what's there
the language gives you no guarantee
about what was in that memory it's
undefined what was in that memory if you
haven't written anything to it
so i feel like we need to fill yeah
yeah that's the first thing we probably
want to do is define that
so i i don't want to find it
define it in malloc because then it's
just going to be overwriting things
but i think we want to do that so chunk
yeah but keep in mind we don't get to
change the interface to matlock and
malloc
does not require that you made an
initialization call in advance
okay right i could just start using
malloc in the middle of my program i
could go
malloc five and that just works right i
never had to say
like i never needed to say init malloc
before i use it so
that that would be changing the
interface if you add another function to
initialize it
i'm not adding a function okay so the
only place that you could possibly
initialize it
is in e matlock it has to be an e malloc
we can say unsigned into chunk index
equals zero so why can't i say
this equals however many zeros or like
2048 yeah i mean yes you could except
in practice that would be like messy
right
but so that would give us a plate that
would fill this with
some pre-defined
you're correct so if you wrote out 2048
zeros
it would be pre-defined but let's assume
that you don't want to write out 2048
zeros so
i would figure that it would have some
no no
you can't okay i mean so the one
operation you have to be able to fill
an entire chunk of memory is memsat
so i'm not sure if you remember it or
not but we we briefly touched memset
um so let me actually let me just pull
it out of my local
man pages so memsat
is very useful for this kind of thing so
basically we have a function that looks
like this
don't worry about the return type in
this case so we're just worried about
this basically says pass along a void
pointer
tell me what you want to set at each
location and tell me how many there are
you'll notice by the way it's using size
t because
that's a it's a memory offset whenever
you're talking about memory offsets it's
always a size t
even though that's really kind of a name
so um
so what we can do is how do we
initialize this memory so
c would be you want it to be null so
that would be zero
so and then s where what's the memory we
want to clear
well that's no i i i don't think this is
a good idea because
the whole point is that we need to have
a check to make sure that like
we haven't allocated this memory already
right i feel like that's an important
part of this
and if we just kind of overwrite this
memory every time we're using it
then well maybe not okay hold on i think
i i think i see where you're going with
this
so so
chat's getting really fired up about
this josh perry it actually on a linux
system it will clear it mainly because
of security reasons
because they don't know what memory was
there before so it'll almost definitely
have been cleared but
it won't be on the other systems that
we're going to be using so
so let's not get into bad habits um
they're talking about putting a poison
pill
in those addresses which is another good
technique but i don't want to it's a
little bit more advanced let's
let's for now let's just zero the memory
so we'll
we'll assume that our allocator takes
the hit and zeros the memory
so
jay don't go trying to give her an
answer she's got to work it out
i'm not even reading chats um
[Music]
what is c again i'm sorry ah let's not
initialize the chunk
let's just one time initialize the
entire thing to be
zero because we we know how much memory
we're going to have for the entire
execution of this program right
but i actually so so i i thought about
that right and i thought about
because we said let's do that let's set
everything to be zeros but here's the
thing is that we have a built-in way
to tell if we've allocated this memory
already which is this global thing chalk
index
if the chunk index is above like we have
that protection already in place
and so we don't need to fill it with
anything because we can just you want to
clear
the chunk that we're going to return
every single time
no but i think so no actually i don't
even think we need mem set
i mean we could just return whatever
happens to be there and leave it up to
the os but let's
let's for good practice let's just clear
the memory let's let's let's say that
our allocator
always returns null cleared memory
right i don't
think so you i i feel like you're almost
contradicting yourself so you say that
like outside of the
the function definition for for emalloc
we can't initialize another function so
we have to do it
but then we necessarily by definition
can only
clear the chunk that we're setting aside
if we re-clear
chunk every time then we're overwriting
potentially
so what if we just that we gave to
somebody
if we do it once yeah let's just do it
once in the beginning
but there's no initialization or
whatever so it means the first time
somebody calls maloc
it
okay let's let's add another variable
which is
chunk initialized and we're going to
start it off as
it's not initialized so it's equal to
zero
and why can't we
return just clear the thing that we
could
except that now we're getting into the
complexity of always calling a mems
so first of all it's faster because i
guess we shouldn't worry too much about
speed but
um it's faster if you just do one memory
blit like if you just tell the thing
like just just clear all this memory
because
right now you're dealing with like 2048
but on a real system like malloc is
gonna have
gigabytes so if you're clearing like all
the time like yeah you could do that but
then you don't know like your allocator
won't
i mean let's just go with like we clean
it up front you know so
okay we can use chunk initialize to
figure out if we've initialized memory
or not so
what do we start with
and then what was c again int c it says
c
is what each entry which each location
is going to have
so in this case yeah zero yep no you had
it
that's null and then except we don't
have to hard code the number
where do we have the number oh
yeah we could do that or i mean you
could also just use
the problem you have is that you don't
know if site this is a variable
like total memory so we don't know if
total memory was ever overwritten
accidentally so let's just
be a little bit more defensive we'll
just be careful so here we're just
saying now
what is even the point then of having
line eight if we're going to call
size of chunk in our code we're going to
use that it seems kind of
we're going to use that for bookkeeping
okay well hey i'll delete it then
no no no no i just do you see what i
mean like if we've defined a variable
you sold me
to be a certain thing if we're not going
to use that it's gone it's sloppy
because i just
just okay so my intuition this this
right now this memsa is going to get
called every time we allocate is that
what we want
i'm not there yet i'm sorry i wanted to
get the uh the because i've never used
really i don't remember using memset so
i wanted to get the syntax down but you
were absolutely right
we are going to put this in an if
oh lord um it's been a while you're
right by the way i mean
that's so we're gonna see if she watches
her bookkeeping or not
but your your intuition's in the right
place
uh josh perry no the interface to malloc
does not guarantee a
zero in it malloc on linux guarantees a
zero in it but that's not
malloc in the standard it does not
require a zero in it
um we're just we're going to do
cleanliness now
and so actually um i can't remember i'm
sorry i was i was focused on this so i
don't remember if your response was but
this
is actually a really good question is
urs rig and i was actually going to ask
you this so thank you for bringing it up
chat um
i'm trying to make sure i say that right
um so
well i guess so so actually to answer
that question i don't think it's going
to be an issue if we ever want to write
zero to the array
because we're just handing the memory
location and if they want to overwrite
it with zeros or whatever they want
that's totally fine
but we're only going to be running the
zero initialization once and then
after that like this can get filled with
whatever and i think you're probably
thinking of
what i believe malloc can already handle
which is that freed memory can be
reassigned
and in our particular sort of like
simplified example it can't be
so actually also something else which
he's worried about the bookkeeping but
we're gonna
i think if i'm getting his well i
shouldn't say his if i'm getting erzig's
right uh meaning right so we're we're
going to worry about bookkeeping because
if we
handle our bookkeeping correctly we're
never going to be looking at the memory
we're about to assign
we're just going to know exactly how
much we need to assign right and we only
pass the addresses we don't
even know need to know what's going
going into that right
okay okay but so we're gonna be careful
about that so
the intuition is definitely in the right
place so um what what's
wrong with this as you just wrote it oh
lord probably something with my syntax i
don't really remember no
syntax is all fine it will this says if
chunk initialize is zero then
mem set it all to zero how often will
that run
once every time no because we're going
to the first time we run this set chunk
initialize to be one
let's did we do that not yet
okay that's that's so that would be
something kind of like at the end
no no why don't we just do that once
initializing you could put it there but
let's put that in the brace
so that it it's related to when chunk
initialized was zero
oh i see what you're saying okay this is
this is kind of just good practice that
your the way you just wrote it would
work too
but usually you want to put that like
wherever you're kind of testing it so
that like immediately you
step on that condition i see what you're
saying this is by the way this is called
a one shot
in classic world
so we're using chunk initialized as a
one shot to basically say have we run
this or not
and the first time you run it clean it
up and you know we can also sneak
any initialization so that this is how
we actually add an
initialization function within our
function you know so this is kind of
like to your earlier point like
malloc doesn't have an explicit
initializer but the first time you call
it it can do some bookkeeping
okay i see what you're saying um all
right so
we can now move forward clearing
um or knowing that our memory is cleared
and so
we can by the way brenner thank you for
the follow i appreciate it
oh um and so
let me think this through so
we need to so
i know we need to return that but i'm
actually thinking through so
we need hold on so i'm just gonna this
might be pseudo code but just like don't
this is the don't look at it teacher for
a second okay so
i'm not looking i'm looking starting
place right so
chunk chunk index it's going to be our
starting place
and really
okay so only the first time could we use
the trick so what we need to do is we
need to
pass off the address to this
yep and so that's going to really be
what we return but it needs to be a void
pointer
so i feel like
i'm not using a mac okay um
thing is gonna equal
[Music]
nice cast
okay that is going to be
the pointer that we pass off that we
return we're going to return
eventually return thing
but i'm not looking right sorry okay
yeah you're not looking i'm not looking
i'm looking at a chat
none of that none of that you talk to
people all right so
stropium no but i should add that that's
a good feature and because
size size underscore t is an int we can
add it to things
so chunk index is going to equal
i don't know if i can plus equals
psi there might be some zero weirdness
here with indexing but i'd like to
see if this would work let me think
about this so
if we start out with zero being the
start and somebody asked for 10
bytes of something we'll give them back
zero the the pointer of zero and they
know that they can fill zero to ten with
whatever they want
chunk index is going to be the size is
ten so zero ten
so we need to be this needs to be size
plus one
really i think
so no because the zero what what if they
asked for two bytes
so if they ask for two bytes they get
zero and one so that yeah
yeah no you're absolutely right it
doesn't it doesn't need to be the plus
one yep
i was okay yeah we're good um
[Music]
okay and then
so let me just go back through here so
we have our initialization
the first thing we do is we clear memory
and then we set it to be you know okay
fine it's initialized we're not going to
clear things anymore
then we pass
the address to the start of the chunk
that they want
and casa's void pointer because whatever
reasons and then
that's the interface we don't get to
choose the interface
reasons and then this is the we're
building uh our version of a traditional
interface so we don't get it okay i
think you can look at this now
i can look at it okay i think i think
it's i'm looking
yeah i i'm it works
okay thing yeah you're doing a little
void pointer out of the address of chunk
chunk index uh
looking pretty nice and then you move
chunk index
forward which is pretty cool so next
time chunk index will be at the end of
that
and we've returned the thing
let's find out i it looks good i
okay now i'm just syntactically we
always
keep our return a little minor knit
um and we usually put declarations up at
the top but
one i wasn't sure if it would go before
after that like initial one-shot
initialization
so i remember us talking about how
declarations go at the top so i wasn't
sure
classic compilers and actually i was
just doing this on stream the other day
when i was doing the nintendo game like
they actually will reject
any time you have an a declaration
that's after code
it'll just reject it yeah like like the
nes the cc65 will just reject it so like
here we get the option because it's
really gcc underneath but
i can tell you that like a classic
compiler will
kill you if it's not here gotcha okay
that's good to know because i wasn't
sure it literally just has to be
up front now in c plus plus we usually
try to put things
a lot closer to wherever they're used um
this this is a pattern which is called
um resource acquisition is
initialization so when we
create the resource we want to
initialize right at that moment
and that's to disallow the ability to
have code in between
like we never want to allow code to
touch it when it's uninitialized
so initializing it on the same line now
the way i've been sort of showing you is
we're just
not using the fast yeah we're we're
doing this which is somewhere in between
the two so
just stylistically that's fine i like i
like the other thing you wrote let's go
we're gonna do that more with c plus you
know but
that's definitely the idiom in c plus
but i'm okay with it
either way for this i mean so if you
want to okay
now martin fowler would say well you
don't even need this anyway because
you can just anyway um so we'll we'll
get to that later but
erzig's point or is riggs point um
we're not rebuilding malloc exactly so
yes just as just as an fyi like this is
sort of like baby malloc
no and urzig no
okay let's try to say it right okay
here's rig you're absolutely right
malloc does not guarantee zero um that
was just
yeah that's just because of this so
no no your memory is absolutely correct
okay okay your memory is not leaking
all right um i got to get a rim shot
that's just
all right um i rewatched a stream by the
way and strophia had a great one the
other day when i was like going like
i'm like yeah let's get our int our
intuition
and it was like strophe i didn't even
realize i punned it i just i loved it
he's very good with the puns so like it
was good
um okay so jay that's an advanced topic
is is the answer to that so right now
we're building a
memory fragmenter version of malloc
malloc doesn't say anything about it
being
as i pointed out to jess early on we're
not trying to build a good
malloc we're trying to build a correct
malloc for right now so we're not
we're not we're not going for the most
optimal yet we're going to start with
getting it right
sorry copy paste yeah it's trophy is
right yeah when you run out of memory go
get more ram you know
that's he's not about a hard drive so
virtual
you know swapping but anyway we're not
worried about that
let's implement implementation details
okay except it's always an
implementation detail because it's
programming
all right so okay
oh so well that's uh no big deal there
yep we add string.h okay i'm gonna add
your assumption
well i'm gonna add the the stipulation i
guess
stipulation
power version zeros
memory zeros they're knee yeah i think
so there's me
zero's memory for you so this is n
off standard um but we're just doing
that
we'll add we'll add a poison pill later
you know we can that's kind of why we're
doing it
okay um
i guess like if i were writing this in a
language that i knew
a lot more in depth
especially since right now it it
wouldn't return anything
i would probably have more sort of like
debugging
checks and things in there to make sure
that it's doing what i'm telling you
we'll do that
let's start with this okay so for right
now we have something that compiles
right
sure okay so it doesn't break as
it doesn't break or at least not that we
know yeah we don't know
okay so what's the first thing we want
to do with it before we start adding
some debugging why don't we
try using it according to the
specification
okay so we have an e malloc of 10 here
all right let's look let's let's let's
use it let's pretend that you actually
use this instead of malloc actually
there's no pretending we are doing that
so let's use it the way we want to
um so here you just kind of like
so let's not do 10 i just wrote that as
a quick placeholder let's
let's let's dynamically allocate let's
start with just an integer
let's dynamically allocate an integer
okay
yeah yeah so each one is
from we have 2048
because wait you don't know the
implement you as the user now
don't know the implementation details of
the allocator
okay so this 64 is you want 64 bytes
no god see that's what i was trying to
do in my head all right there we go you
want eight bytes okay
or if you didn't want to remember it
because you want to write it to be more
portable
you could use you could have the
compiler figure out what the size is by
doing what
sizeo yeah so let's do that okay
oh you're gonna make it unsigned okay i
was just making a regular in
okay and
okay and where let's store that let's
make a new in pointer that's gonna
take that value um
so i need to do that before this um
okay so we'll just call it um
uh other thing other thing i like that
other thing
okay um what type is that so
nope nope no no no
[Music]
i want this to be a real pointer because
i want to cast it
i don't know how to cast how do you how
do you make something a real pointer
from a void pointer
you cast it to a real pointer type how
do you do it well first of all what's
the type of other thing you still didn't
put the
real point okay sorry yes i'm
okay that needs what are you saying that
other thing needs a type what what
what type is it what type do you want it
to be
a pointer not just a pointer what kind
of pointer
a real one yeah a real what what kind of
real point
we've talked about like what what what
type is it going to be
i mean what what what are we putting in
there how much memory did we allocate
oh i oh that's okay so here's i'm sorry
this is like
we've done the the file in all caps
right and we've done void
but we've never really done like yeah a
pointer to oopsies
a pointer to something yeah that's it
that's how you do it
and so okay that's a concrete pointer
that that that's an in-pointer
okay i have a question now it's exactly
the same size as a void pointer
so i have a question about that it's
exactly the same size as a care pointer
it's exactly the same
size as a size t pointer if i can why do
we have to say what it is then because
it's just an address
semantics they all have different
semantics last week we were doing
struck planets and we did struck planet
pointers
right so our concrete matter it's just
an address oh it matters
it's i mean like just so it knows what
to interpret at that memory address
okay all right that makes more sense
right yes
so then we need to cast it no no no
don't initialize it
let's keep using your existing you know
yeah we declare on one line
said the initialize as a as it was a
fantastic that's
that's c this is c but i like it okay um
yeah that's how we turn it into a real
pointer
i like strophium's comment too it
becomes real by proving itself brave
truthful and unselfish nice
don't tell her strophium she it's that
she doesn't need that detail right now
but
he's right by the way i don't know what
that means but okay um
no josh perry stop it that's c plus plus
we're not doing c plus plus stream says
c we're doing c
lord all right i'm like not even there
yet so casting gets even crazier in c
plus casting is really cool
and it's i really like the control that
it gives me
over exactly what's happening because a
lot of times no no there's there's
casting in c plus plus there's just a
lot more of it
what i was getting at is that sometimes
in python because
things are are like so much of the
control is taken out of your hands a lot
of times especially when you're
importing different libraries and
whatnot
that you can run into a lot of problems
that way
and so i kind of like how much control
this gives me over being very explicit
about things like i know
exactly what is happening just nice
i have to say one thing this is not
aimed at you this is aimed at
nightshade dude okay
shaking my head okay all right i'm i'm
shaking my head nightshade dude okay
okay
everybody so i'm sorry really quick
you're right by the way it's very cool
how the casting gives you the control
but it is really up to you as a c
programmer to keep it straight
i know like very little c even less
c sharp and i'm very very comfortable in
python and once upon a time high school
jess new matlab
so i've heard so much mostly people
dunking on
but i've heard so many things about rust
and they're all
memes so i have no idea what this
language is
don't don't don't don't feed the trolls
they're they're rust or bust they're
just they're they're getting a little
crazy
it's all the jokes about rust but like
jay i don't
hate rust jokes about rust i don't
actually know anything about the
language itself so now i need to look it
up this program is a little
rusty opening pandora's box i'm opening
pandora's rusty box
okay um
so okay right other nice ones i like
that joke
we have a pointer to other other thing
is an end pointer
and we have cast it to
whatever malloc gives us okay chat's
cracking me up sorry
back back serious implementation but i
want to
then i can say
so
me the thing okay so actually i don't
know if this is going to work
hold on hold on so other thing right now
is a pointer
it is an address in memory and i want it
to
give me i want to be able to assign
the thing
that's for structs that's for structs oh
it's only the ppu operator is only
qp only applies to struck pointers no
oh my world is crushed it's okay it's
okay
we allocated one int we're gonna get
back to our
pointer basics that we didn't we sort of
glossed over earlier
yeah boring i don't get to use the cool
arrow
and reading that statement it reads as
it reads as the um i am dereferencing
the pointer the address of memory so
it's getting the thing at that address
it's sticking 12 in there all right
let's try that
and we print it out because we want to
see some output
using the custom allocator
well i mean we already did our custom
allocation but
yep
nice okay why are we closing the
parenthesis
oh lord why am i
let's get a question okay
oh oops yeah this happens sometimes
right this
is wait no no no it's an integer we want
it to be d
you were right the other thing was
problematic
can i make it a long decimal though no
no no don't don't know it's an
it's it's it's d it's okay but what
what's it actually thrown about
hold on format well first of all the
number is nowhere near 12 right
no no i know so hold on give me a second
so percent expects argument of type in
but argument two has type in
oh it's a pointer oh oh duh duh um
hold on so
oops not that one this one
hey party time okay
now i have a question okay now you got a
question of course i want to see another
allocation
memory address negative ah that's
because of the semantics you added to it
what are the semantics you added to this
pointer
what kind of pointer is it oh should i
i've specified unsigned int
well if you want to deal in ins no you
should be
talking about hints no but the
the the pointer should have been no no
no it's
it's pointing to an end the point yeah
the the concrete type had better match
the pointer type like you you generally
want them to be the same except when
you're doing this void pointer you know
that's not the problem
no it's not that it's it's trying to
interpret a memory address
as a signed decimal as a signed
int and so that means that there's
something in the high bit
because you know if we're dealing on a
if it's 32 bits for an int
or 64 bits for an in that means that the
high bit has a 1 in it
which is going to cause it to
show up as a negative number high bit
sorry that's a joke but um is that the
first because when we were talking about
bits and how the sign is going to be
that first
okay all right yeah it's that two's
complement thing but yeah that that
high bit definitely tells you that it
was negative and so it's just saying all
right you want to print this thing out
as a
signed decimal integer fine i mean it's
that's negative then
gotcha okay okay oh and thank you by the
way dutch
that's a great name dutch caffeine
there's all sorts of wonderful things
happening
is that just a coffee shop for the dutch
dutch have other forms of caffeine
clue us in the dutch magic yep
all right we'll speak about the
netherlands later let's let's uh
let's let's do another allocation get me
a job okay yes
and by the way jay thank you also for
the follow
not a coffee shop okay not a coffee um
hey sonny what's up
hi funny all right so
i am going to sing ho
i'm gonna just copy this for the notes
all right i like dinosaurs hello guy hi
sonny
all right sunny's my mod hello sunnymod
okeydoke so now we need to do
free no no no that's not free let's
let's do another allocation let's see if
your
program i mean that was just the first
allocation that was kind of the rigged
case where it was like the first
piece of memory what about later on i
see what you're saying okay so
let's see another allocation everything
the same i'm just gonna pick a different
yeah a different integer
clear the output
okay so that's looking like it's
operating correctly now
let's let's let's let's beef it up a
little bit let's okay
let's allocate so we that's our first
allocation was this email lock
all right so we have one called email
like let's let's do another email lock
call
this time let's allocate five characters
so five five in a row what do we call
that
an array yes that's it let's have it
okay let's have an array of five
characters dynamically allocated by
e malloc so jake goes i bet 10 bucks is
going to crash down i think
betting is against terms of service i
don't know a twitch but you know i
i wouldn't be taking that bet but let's
see let's see what happens
five characters huh my name uh-huh
hold on leave leave that in leave that
in i want another allocation i i don't
want this
this reusing thing we we already
allocated that in that's our first piece
of memory it's burned it's gone
let's let's do it no no no let's do five
bites
after it let's i want that first in to
stay live on the
the jess heap and then we're gonna get
to the next five bites
well copy and paste exists all right um
sunny what kind of precedent are you
setting for the channel
don't no no betting in here
other other thing nice
you know it's it's the little things
that get you through yep
yep sorry the rough days of programming
except we don't get to assign a raise
like that do we
no no i'm not i'm not done hold on hold
on don't look
okay i'm not it's not your turn no
looking yet
totally looking totally looking okay
yeah i like oops
idea here let's put both printfs at the
end to make sure that they're both live
on the jess heap
well the chunk really it's
a chunk so you've got to like
if it makes you laugh yep i want to see
it
let's get it on the trunk okay i this
isn't ready for you to look at yet i'm
trying not to look um
yeah don't look um so
[Music]
because a pointer
okay so that's this this this i think is
fine
there's something else that's bothering
me here which is that
wait a minute you just allocated five
pointers
no you don't you don't get to do the
allocation this is dynamic
okay
and so let's see but
man nathaniel is up on actually i think
i'm going to do this because it's an
array
right and so i'm going to use my array
hack
because i know that um
talk to chat i got to make mistakes and
think it through and i know this is not
right yet i'm not there yet hold on
all right so um
[Music]
so actually what i need to do here is
because right so
so this is
some point i'm going to need this which
is
a replacement for that because
it's this instead of this
um
and here's the thing though
here's the thing is that
we can so a
an array an array is just technically
a pointer to the first element the
pointer to the first element in that
array and so
i'm setting that this is an array of
five characters and then i am
casting but technically technically what
this actually is
is a memory this is actually this is a
pointer to the first
element in the array okay
so it's already pointer so it's okay
it's just the same thing i was doing
before because it's an array and rays
are weird
and so then the other other thing here
i'm just casting that instead of being a
pointer i don't know if i need to cast
it
it kind of already is i do because e
malloc
is going to be giving me
a void pointer so i need to cast that to
be i think
character that would make sense because
it's a it's a pointer to the first
character in the array so it would be a
character pointer
so that's okay and then i can copy
that into this which
technically is a pointer but it handles
it okay because i've done this before
um okay all right you can look at it
i'm not trying anything
[Laughter]
all right okay
i have to work through things sometimes
no it's totally fun it's totally fine
but i i have a lot to say
about this and i'm not saying anything
all right so let me at least walk you
through i don't think it's right but i'm
not really sure where it's wrong
okay um but let me kind of walk you
through my thought process here okay
so i love line 32 by the way
oh no okay i like i like what's going on
in line 32. no
line 32 is wrong line 32 is wrong it's
slightly wrong
it's slightly wrong it's not all wrong
yeah yep that's that's looking good
that's that's what we want to ask for
and no no spaces are fine we don't need
to be you know
i like my spaces all right i really do
it helps me read it okay so
right so with care other other thing
five my thought process here
is that when we learned about a raise i
remember you telling me
that some of the weirdness with using
pointers and arrays arises from the fact
that
technically the variable that we set to
be the array
is actually a pointer to the first
that's true but that's syntactic sugar
right now we actually want a pointer
which is going to go to the first thing
in the array
what is this allocation we have on 31
what what what are we what are we
declaring on line 31 i mean
i know the comment says we're declaring
a pointer to the first element in the
right but
the compiler doesn't read the comments
yeah technically what this is is it's an
array of five characters yes
that's correct and that's the problem
so then if you want me to be explicit
and there's like no syntactic sugar
allowed
give me one second because i actually
think i know what to do so here
hold on we need we need the address of
operator
wait wait wait wait wait
right
the pointer to the first element that
would probably work
but that's that's some evil c you just
wrote so
let's okay let's take a step back
we want a care pointer which is going to
point to this dynamically allocated
array
now before we changed what was happening
on 32 which i mostly liked what was
happening on line 32
other other thing is going to get a
casted care pointer we're going to take
the void pointer we're going to cast it
to care pointer
of e malloc of size of care times five
so if our memory allocator works fine
that's five bytes and
the first the address of the first byte
is going to be returned in
other other thing except other other
thing
is not a pointer it's a
array of five that you're referring to
the point or the first
address technically arrays are just
pointers
it's true but it's a little evil why
don't we okay why don't we make this a
real pointer
wait okay so before you before you do
what you can can i ask you why could we
not just
why wouldn't this i know you said it's
evil c
but i'm really not sure why that's why
it's evil yeah no it probably would work
actually it it probably would work but
it's evil it's very explicit it's nobody
give me the address
of the first element and set that equal
to which which is a pointer to the
that that array but the problem is that
you're talking about stack memory here
you're then going to overwrite that
pointer you're not going to point to the
array anymore
which is probably going to cause the
compiler to freak out at you with a
modern compiler
and you're going to go you're going to
go pointing to somewhere else that e
malloc is going to be giving you out of
chunk
so let's just treat this like what it is
i see what you're saying which is
initializing a real pointer
i just want to make sure i'm following
you so the way that i had done it so
really quick before you fix it
because i think i see what you're saying
when we do it like this
the problem is that we're initializing
this in stack memory
which has its own memory address then
we're kind of saying
take the memory out of this thing and
stack and wait yeah let's let's go
overwrite that type so
i mean we might the compiler if the
compiler's not very smart it'll work
just fine
because it'll go fine that's a pointer
but i see what you're saying okay so i
guess my
issue with this was
so we we here is a pointer
a care pointer fine we're we're well off
and good here
and we can this this should be fine yes
we don't okay i see my problem i was
really worried about somehow needing
like okay i i'm goofed with the arrays i
was really worried about it like
knowing that this was a pointer to an
array of a certain dimension
but that's taken care of right here i i
had to go to duct tape
okay i just i want you to know that i
had to go to duct tape for this like
because i was like biting my tongue on
that one like because
that's how people learn though like i
don't allow for the experimentation
right
um okay so uh
nathaniel i think she had a no she
leaked memory the other day that wasn't
a buffer overlook over
overrun but um yeah let's let's
kind of see what happens let's uh out of
chunk yes
see see here's the thing is that like
programmer so i love i love
of the future 2000 years from now are
going to be like
what is what is like the you know
etymology
of using chunk to mean like you know
this pool of memory and it will trace
back here all right
you've heard it first here well the
funny thing is that a lot of these
things use
thunk allocators but i'm trying to
resist like getting into that that's why
i was trying to use the right term about
pool but anyway we'll we'll get the
thunk and i i promise i will remember
that it's pool
when i'm writing the first pass don't
make promises
you can't keep all right anyway let's
remember
okay um okay so so
care pointer we point it to e malloc we
get a result
uh hopefully five bytes we assume that
we always got memory because memory
never runs out even though we now know
exactly when memory is going to run out
because we've written our own allocation
so this gets back to like this assert
idea like i know you said no it's going
to do that because it's debugging yeah
right but i
i really want to put something else in
here but i i thought you would say no
that's like debugging and
yeah but yeah no asserts they definitely
know a search okay
fine can i say because i really want to
put like a
oh you could write warnings if you feel
like it i mean that's that it's that
if if um
index plus
size is less than or
equal to oopsies um
is less than or equal to 20 48.
we don't know no magic numbers no magic
numbers what what is
another way to refer to that yes thank
you
right oops that's not right
and then
this bit
otherwise what i'm my mom
else
[Music]
um
oh sadness
right because we need to make sure that
like i know i know
except this is a well-defined interface
we have to do exactly what malloc does
on the interface we don't get to change
the interface i'm not changing the
interface it's returning its voidness
it's taking
whatever now you're not returning
anything in that case
just gave you the best thing it was such
a missed opportunity
no dutch caffeine naughty by the way
dutch caffeine to your earlier question
this is uh we're learning c as an
additional language um
jessie is a python programmer
astrophysicist and she
you know does various things and wanted
to learn some c so we're doing some c
and what better way to really get into c
than to build your own memory allocator
and by the way they were asking uh
erzerig was asking what the equation is
on your whiteboard oh so that is the
equation for reinforcement learning
and so if you want to add that to our
scotch discussion for later
i love talking about reinforcement
learning yeah machine learning and so we
could talk about it then
but i also don't want to um uh take away
from
the chalk yeah we gotta finish her
can you let me do something yeah let me
do something
just don't change the interface of
malloc don't don't change theaters
okay
i don't even know what i'm looking at
he doesn't see it don't tell him what
you don't see you think you don't see
anything
what what what what
what
there's a scrolling bug in this thing
chunk alloc okay
fine we can call it chunk chunk alex
great i love chunk i like let's let's
let's go with that
all right you're allowed to change the
name of it but you're not allowed to
change it
i didn't change anything else you're not
allowed to change its interface it has
to be the same interface
it was it was it was sonny's comment
about this better replaced
gem malloc and i was like wait this is
e-alk that's such a terrible name for
something that's so chonkalicious
yeah so i delicious
i wanted to put a safeguard in there in
case we reached
the end of of dutch caffeine that's
because this is
that we're building malloc we were using
malloc and so this
this whole project is about
understanding what malloc does
and yeah rebuilding it so we're keeping
backwards compatibility and
we're not allowed to change the
interface because jesse has been trying
to change the interface on us a few
times but
you don't you don't get to do that a lot
in programming you have to deal with a
legacy interface and you could do any
sort of magic you want in the routine as
long as you
conform to theaters compatibly has to
support winter zombies
yeah well this is malloc we're
supporting all the way back to like the
1970s here so
there's quite a story on this one but
okay
so now at least i i wanted to put like a
safeguard in there but then we had this
conversation about
exit zero should solve the problem i
don't know what that means no that's the
troll that that
he's basically saying you just quit the
program
i would like you know but i you don't
get to quit the program that's changing
melody i returned no yeah you returned
the right thing
matlock returns null is there a null
pointer do i need to have a pointer
since it says
no i said sorry pointer it's zero zero
does zero have units no the reason why
i'm asking is because
in our definition it's philosophical
specifies what it's going to
return so i didn't know if there was
like a pointer
that i needed to return here yeah but
null turned into a pointer
here that's because it's it's memory
address zero
if you interpret null as a pointer okay
so
it's just like no all right yeah like if
you get into c
plus they're actually distinct there is
a null ptr
thing and you know that anyway it it c
does not differ it's actually just it's
the number zero okay yeah
i just wanted to be like nah like you
messed up
yep and you dereference a null pointer
when you try to dereference zero
okay so okay we have some confidence
that our
implementation is correct right yeah how
do we get more confidence how do we know
that we got this right
you try it you see what happens why
don't we starve it a little bit
let's let's have a little fun let's
let's look at all this memory you've got
oh now there was a reason i kept telling
you don't go littering your 2048s all
through your code because
fair enough we're gonna go yeah 2048 is
not a realistic numbers and our program
shouldn't care
right it should be correct no matter
what the size is
okay so if we give you only three bytes
what are we gonna do
well hopefully we'll get the out of
chunk error message yeah
let's find out hey
segmentation fault i love it
so i want to figure it out so hold on
hold on hold on so
oh this is weird it's like cutting off
um can you read
the output like my browser's being a
little bit weird oh no here we go i got
it okay
so so it does the first thing right and
we expect it to fail
and but it fails in a way that i'm not
expecting which is that okay warning
format
s this specific care star but argument
two
i said oh this is like that weird hold
on hold on
so this is um
because i i this is left over
from this is left over from from this
which is that this needs to be
give me hold on hold on address of
operator d reference operator
that needs to be this i believe i'm
sorry i miss which line you changed
uh 41. so i think that here i was
trying to i was changing
the the i was trying to copy
the string that is my name into
the pointer which doesn't make sense so
i need to be copying it actually
into the thing that it points to no it
was right
right you know because stir copy
actually takes a pointer
so it yeah no no that was right that
wasn't the bug
in fact no i see the segmentation fault
but before that there
is this error on
like formatting error saying something
having to do with my percent s
wait that's line 44. but it says look
warning format yeah
s expects our argument of type care star
so it expects a pointer so that
care pointer but argument to us type int
yeah other other other thing is a string
so don't change the type of the output
it's it's supposed to be a string right
so
i think that might have fixed it no that
fixed well yeah i mean that was that was
the warning
but no but it took it took away the
other problem
i was fixing errors one at a time and so
this fixed the
the first error but then this error
yeah we seg faulted we we don't have
that memory
which is actually what would happen if
we didn't check the return type on
matlock right
i mean if so if malloc returned null
which how do we know in this program if
it returned null
so let's let's look
so is the problem that because it
returns null later when we try to
but why is it still not it's not giving
the error message
um so i'm guessing that you know
chunk index plus size is is
much smaller than three right and so
the problem here being
so hold on hold on so this should
this should trigger because this
condition is met
and then oh sorry not this this
should trigger because chunk
index plus size is not less than or
equal to the size of chunk
and so it should print this and return
no
we should at least get that print even
if we get like a fault later we should
get the print
but we don't and so
that makes me think that it doesn't it
somehow this condition is not
is being met so i've written it wrong
sonny what are you posting image links
in the channel
so chalk index
every time we run this it it should set
zero
and so it should initialize it should
clear the memory that we're interested
in
chunk index should be zero and then
zero plus the size in the first one
i mean it should fail with the first one
oh i just didn't know
sonny that's why so
i'm just feeling with the first one so
then wait why don't we see how far we
got let's let's try
let's let's do some print f debugging
because we don't we're not allowed to
use the debugger yet
so hold on hold on um
if this is met i want to see i want to
see if this is what it is uh
that's new line so that we make sure we
flush oh yeah thank you
okay good so this is not met well
let's see let's see if we let's get back
to a positive case because right now we
don't know what's
failing so start right at the top of
chunk outlook
how do we know the error is there
yeah we right now we don't know where
it's failing
so it's not even starting so hold on so
it's got to be something here
this shouldn't cause oh my lord um this
shouldn't come
right that's just a pointer that's fine
well so
this this is where
let's see oh it's not updating did we
lose the stream
um
i'm watching stream it looks like it's
updating um
oh the psych fault's happening over here
everybody
she just cleared it so here we're
so we're not even getting here yeah so
we can't even really trust printf is
what we're getting at
so and this is this is one of those like
early in it things so anyway we know
something bad is happening
we know that our program isn't dealing
with it let's let's assume that we get
through the first allocation so
i'm gonna give you the four bytes but
you know what i'll give you eight bytes
so let's let's just see if that starts
giving us some output
no no because this is this is much
bigger i need much more because this is
an int
so don't we need no we should be able to
get that yeah that should fit well here
let's
give it 10
okay so something funky's happening
hold on let me clear this and run this
again sorry okay
so the rest getting here static
yeah you know maybe there's a problem
with the obs has really been acting up
there's some tonight aside from the
mouse oh no yeah
yeah yeah when i change the huh so we
can save it and try to refresh
yeah why don't you save it i'll
hopefully have to rebuild that again
i'm just going to copy it just in case
all right chat i have refreshed it
yeah it is definitely all right i'll
set it to that accept that
okay hopefully that is updating now
yeah yeah okay cool yeah obs is not
liking
focal i just want a new version of
ubuntu in there we are out of sync
so at least according to i'm like
watching you have output there
and i've cleared it and i refreshed oh
oh
gotcha all right let me refresh sorry
all right so
now when i do this uh yes
okay now do some spaces or something so
i know that we're in sync
yeah yeah okay i see you editing yes
we're good okay okay
all right so um cool
yes very good um
sorry about that everyone
all right um okay so
right more seg faults please okay they
want the seg faults back we got to give
it the same we're working on it
okay we're working on it so let's start
the memory again all right so back to
three bites and
hey there we go there's your there's
your seg fall i love that the stream
screwed up as soon as we seg faulted
that that
makes me happy in some some deep part
okay so i think the the interesting
thing to me is that it's happening
i put a print statement like basically
right here uh line 37
in main i put a print statement there
and it didn't print out
right so it's almost like somehow when
you set it to
three mm-hmm
so when we made it four it failed
two yeah when we made it
it failed too and when we made it 10 it
worked
it was fine let's try nine oh okay so
that seems to be the bite
so something seems to be going wrong
with that first
move or something something after i mean
so we know that here's chunk
what are all our references to chunks so
changing chunks seems to be
what's causing trouble so um we can look
at chunk index it starts off zero that's
nothing
nothing can go wrong with that and chunk
initialize starts off with zero nothing
go wrong with that
so the only real action is sort of
starting down here so we have this
other thing and other thing is an in
pointer
which comes back from here and then what
do we do
now we know that's bad in the case that
chunk alloc returns null
yeah exactly okay but we're assuming
that the output is ordered that the
output is making it out before the crash
happens
the output is making it out before the
crash happens when oh you're assuming
the null
well so that's why so we're assuming we
see that print out
it shouldn't even try
to return but wait okay hold on so i
have a question
so before when when everybody was kind
of laughing about like no
you said that it's a pointer to the null
like to zero
yep right well it's just zero it's null
is the number zero
the problem is is that we need it to not
like i understand that okay
the syntax or whatever the system i
forget the word used
requires that we return a pointer i get
that
the problem is is that if we return a
point i don't know why the printf isn't
working
but that it's trying to is it trying to
grab a piece of memory that starts at
zero the zeroth place in memory let's
not
yeah and then it's trying to write
something interesting it's writing to it
which is the problem
but it needs to we need it to like
return basically not a pointer
no it's got a return null because that's
what matlock does
so why isn't it printing at least no
that that's what i was addressing
so i was saying that we're assuming that
we see the output
before the program crashes
well before it even returns nulla should
print
right that's just like how the code is
written
do we know that the output makes it out
before the crash happens
i mean the only other way that is is
that somehow printing this crashes it or
our initialization crashes it or like we
don't even get this
wait we don't even get the beginning
chunk a lock so we it's not even
initialized
something else is we know for a fact
that this line
is bad yeah like we know that if it
executes line 38 it's going to crash
hard
yeah now the question is do we see the
output before that crash happens or not
do we know well right now we don't see
the output but
you know we don't know if c is going to
give us that output or not
we do know that when we give it enough
memory it works just fine
but the question is is like and we see
all the output
why would we not we don't even get even
if i put even if i only
before we say why a print statement it
still doesn't run that wait
before we say why why don't we try to
test what's actually happening
because we don't know what it's doing
right now right by definition we don't
know what it's doing right now it just
says it's a segmentation fault we don't
know when it happened
okay all right so let's start with
if other thing is
null then
something bad happened
let's just stop execution we'll throw an
error
how's that sound sure all right
we run it now this is fine because okay
well exit you're supposed to
add in standard libs so i'm going to fix
my code and add in standard lib
and we so now we have standard lib
execute this thing and now this was fine
because we had enough memory but when we
had not enough memory
look at that
how does that doesn't make any sense
it wasn't about making sense it was
about what is the computer doing
yeah i have no idea making sense is a
very human concept
look c is just giving you the tools like
it's kind of like
what it does is a little bit undefined
when you get a segmentation fault
so what's actually happening here is
you're actually getting a race
between printf which is trying to give
you the output
in the right order but that's a buffered
io stream
and the program is crashing so if the
output doesn't escape before the program
crashes
you're just going to see the
segmentation fault
i guess that doesn't make any sense to
me because i feel like
so that implies that it's not running
things line by line
it is running them line by line except
that this is an imp this is sort of a
leaky abstraction because
printf does not actually print at the
exact moment
that it's called oh
that seems kind of useless well it it
basically it's telling the colonel like
i want you to write this thing i mean
there's there's
a bunch well it does some formatting
stuff and after it's done it's
formatting stuff it then says to the
kernel
okay i want you to send this to the
standard output stream
and then the standard output stream is
supposed to take its little time and
send the thing out to output
now because that's a system call it
depends how it's implemented but because
that's usually a system call
like your program's crashing before that
output is getting out there
but i guess to me
that seems like really bad design for
print apps
well uh maybe kernels i don't know i
mean it's just
i mean like what's the point of having
printf if it's not gonna print
well so it it because printf tries to
print
in sort of an efficient manner it
doesn't stop all like it doesn't stop
the world to make sure
that that made it out in order to do
that you have to use what they're
mentioning in chat there's something
called
flush you need to flush the output and
that literally says
do not continue until this thing has
made it out
yeah i like that that's kind of like the
assert right yep
yeah that's what i wanted to use earlier
okay you can
accept it's not a certain assert is very
different
but it's like a similar concept that
like you do not pass go
unless a certain thing is done okay so
right
which is like very useful those kind of
gate gates are very useful because then
you can like
scatter them throughout and really sort
of narrow in on what's going wrong
this right especially if like print f is
not something that kind of business i
i like i let you struggle with this for
a reason
c does not always tell you what it's
doing okay like in particular you don't
know exactly it's not that c c is pretty
literal
but you don't know exactly what the
system is going to be doing
under you you know like you don't know
exactly what this library does like you
don't know that the assumption is hard
that
this stream has to be flushed before it
continues
or not right that's it probably it might
say that in the man page it might not
i mean i'm not 100 sure it's i mean
like getting used to buffered io like
this is kind of a common pattern
it was done for efficiency like so it
sort of like tries to like buffer up a
bunch of memory and then flush it all at
once so that that way like it's
efficient on you know
the way calls work and this gets into an
old like you know
a thousand bytes writing a thousand
times versus writing one right that's a
thousand bytes
the one right that's a thousand bytes is
a lot faster
so it this kind of gets into the world
of buffered io but it's it should be a
hidden implementation detail it's not
here
so in this case your segmentation fault
despite occurring above
is eating you not in the order you
expect
it's not running it out of order but in
this case like the printf is
like it's being passed off to the system
which may or may not have sent that like
printf doesn't guarantee that it
immediately came out
flush does that yeah like you have to
f-flush it to actually and and this is
flush says like i want oh that's the uh
link so i'm making a note of that sorry
i like this thing
here i'll i'll i'll pass you the uh this
is the the actual call
i just pulled it out of the manual page
and flush
does do that right so you pass it a
stream and
it will you know flush that stream and
it will not continue until that stream
is flushed
so that does guarantee you're sort of
ordering how would you use that i'm
sorry so it takes a
file yeah
so yeah you can flush any file
including standard out
i mean it depends how it's defined if
it's one of those like
can you kind of show me how you would
use it in this case because i'm still
not sure what you mean by in stdio you
actually get this definition
so this in the current version of c that
you're using
standard out is defined as a file
pointer right so it's actually when
you're print defining you're just f
print defining to standard out
and that's a file yeah it's just a file
it's it's treated as a stream like
anything else before we treated them
separately when we were first learning
but actually they're
they're not it's file semantics and just
the same way with file semantics how we
don't know if something was written to
disk
because the program execution will kind
of keep going like you know it'll
because
disks are slow you know why do you want
to wait for it unless you really care
about it you know it's like no i need to
know that this happened before i keep
going
like for example when i save if i do a
save i want to flush that file i want to
make sure that it's saved before i keep
going i don't want to keep executing and
potentially crash and the save is like
screwed up
okay so i can flush that right and then
i will see it
so i can just flush standard out i don't
really care about the return value in
this case i just need to know that flush
happened
so i could i could throw an flush in
there and it'll happen
and now i can remove my
my check that i added before and i run
it and this time
we get the we get the output because we
were guaranteed it we we said no no no
you don't keep going until that thing
makes it out so
despite the fact the seg fault happens
and that's you know it's mixing up the
output because i'm printing standard
error before i'm printing standard out
that's a that's the implementation
detail of mine
but um that's pretty much what happened
so is there a way then that i could
build that
into the the the definition of chonk
alloc
that we sort of like because i guess
the the print statements aren't super
great
in the sense that it's going to like
return this null or whatever and
it's still going to continue and it's
going to break before it can print it
is there some way that that's how real
malach works by the way
the forced flush into it no but that
that's exactly what real malach does
well what if we make better melody okay
oh well chunk
chunk a lot can do that so all right
exactly yeah go ahead you can add the
flush
can we do that like in in the else
somehow so that it like knows okay you
need to print this before you even move
on
sure and by the way that's what erzrig
is like
see we are your sole partner here
my my code soul oh sorry chat ran away
i'm sorry
chad i missed that we were getting into
some debugging
um not printed i was i was reading chat
and just writing things
yeah nathaniel knew right away about f
flush that surprises me not at all
uh what should malloc zero return sunny
you're trolling me that's just it's it's
one of those
fun philosophical debates like you know
there's a great bit in like the bsd man
page about it which is like
malloc zero returns zero because it's
it's a dumb answer to a dumb question
like they actually i forgot how exactly
how they worded it but let me see it
might be in
linux man page too it was
yeah it's always always no they don't
they don't have it in this one i
i think it's in the bsd manual pages but
anyway it was a fun
it was a fun one um
and the yeah the the new line doesn't
it should flush but it doesn't always
i'm not sure if she had the new line in
there or not jay
um performance if you have flush every
time nathaniel is correct
yeah there's a small performance hit to
adding f flush which is why it's not
that's why printf doesn't flush by
default by the way it's it's about
performance
uh harris studios no this is not her
first programming language she's been in
python for a while oh
sorry you already answered that yeah
yeah no no no malloc
yeah don't do that okay yeah that sounds
like a bad time
um all right so um
great that's um that's that that there's
a little bit of torture for you that's
that's the fun of real c
no i mean that's that's really good to
know because i think yeah that's why i
didn't want to skip past it because this
is something where like it just
it's confusing you're like no why is it
not printing my thing it's like well
guess what it's kind of interesting
because i just
it's a leaky abstraction in this case
because it oh and thanks for the follow
by the way
um it's a leaky abstraction because it
requires knowledge
of buffered io but it is probably there
in the manual pages i mean just one of
those things
and harris studios giving you the feels
because
it would have been pretty brutal to
start with c i absolutely agree
but at a certain point though like yes
it's brutal to start with c but then at
a certain point
not brutal i think that's a hard word
but like it almost becomes brutal
continue with python
i think harris is not wrong are you
under yes under the surface that at a
certain point and this is where i hit
and reached out
some coding guy for figuring out you
know how to learn c is that at a certain
point
you realize just how much is being done
for you and how much that's kind of
hampering your understanding of the
deeper systems
and so as much as like we joke about c
and i like i love to tease about it
being
you know a little bit obtuse sometimes
it's
it's very helpful well even an extremely
first conversation
i said to jess like i will teach you c
so that you never use it
i mean that was part of the comment like
it will make you a better dev
there's no doubt but it like i i hope
you don't generally use
like i try to i try to write in as high
level languages that i get away with
when i can
but sometimes
exactly like yeah that's true my
my background is not i didn't have a
formal computer science
uh education and so i really taught
myself
how to develop and everything and so
part of the problem right is like to
to erzrig's point is if you also don't
know
sort of like the formal education around
programming at a certain point you're
going to have to step away from those
like higher languages
and and learn the nitty gritty stuff i
probably won't ever be a c developer
all right just just putting it out there
don't say that you could be you never
know
i will say this so i think you'll
appreciate this guy but um
about four years ago
no it had to be even less three years
ago i was like i
literally remember saying to somebody
shoot me if i ever say i want to be a
software developer
i hate programming i hate it it's the
worst part of it's the worst part of my
job
and then like literally fell in love
with it i'm like oh my gosh
don't don't get into a discussion topic
i want to have bourbon if we're having a
discussion time okay all right
it was just a quick it was a quick
anecdote we only did half of our test we
didn't get to free yet
so um by the way brenner i i wouldn't
say that i disagree i would
agree that's exactly what i'm saying i i
think that c
is a great language to learn when you
really want to know like how the
computer works i mean assembly
is even better but i feel like there's i
think you got to get into all these
things at some point
i don't i before we do free you answer
chat i'm gonna use the bathroom real
quick okay
um so basically to that like i i don't
think that it's
um like to some sense like i still think
that c is like a great rite of passage
to a developer that's
especially coming from just higher level
level languages because so many of the
details are just sort of done for you
and that's good because you're usually
thinking about
your algorithm or your data set or
whatever you're actually trying to get
done but
on the flip side like it also that that
level of abstraction can sometimes blind
you because it just
leaves you it is like you're not really
sure how a lot of the stuff works so
you don't necessarily know when you're
making you know crazy assumptions on the
computer because of how you wrote in the
high-level language so
i i i really do think that like there's
something to be said for
c as sort of a reasonable abstraction
over assembly and then
assembly just because you know at some
point i think you gotta know
not that you're gonna be writing a lot
of assembly but um
yeah not saying an enterprise
application see just so understand that
it's under the hood
when they program teaches you good yeah
i mean i've also seen a lot of bad
habits too insane by the way
but um i think you should either learn
x864 or some type of risk assembly just
enough to know
yeah i agree nathaniel i would even pick
something simpler like
you know i mean risk being it depends
which risk but i mean something like
6502 i think is fairly ideal it's it's
not risk but it's sort of like
there's not a lot of registers it's
relatively easy and
x86 64. there's so many address like the
complexities
really high not that i think it's a
waste of time but it's
it's almost a bit more advanced these
days i mean i think like even like
old school x86 is probably you know
better as a learning language but
um or something like pick which got
brought up last
week and i went and bought a development
board
but i don't see the the pic people here
tonight
but um this this is another fun kind of
assembly
world there was the
i i really like the uh the risk five
stuff
that's been kind of going around it's
not licensed or anything like that
urgent wrote assembly for a living for
10 years wow that
givers rick a drink please assembly
cobalt unfortunately yeah i mean it
depends like you know
coding's coding you know they're they're
all touring complete i
like i'm not gonna go choosing to write
stuff in like cobol or fortran
well fortune's not that bad but i mean
i'm not gonna it's not gonna be my first
choice for like a web
thing it's seems like reviewing
not optimize assembly that your c
compiler generates just as valuable
that's true too
josh um 68k yeah i really
68k was i think my first assembly no
that's not true i had that ti-99 4a with
a
crappy non-6502 uh like glass of red i
like lots of registers i like avr
assembly
um and mips some yeah i
i mean these days i would go with risk
five just because why license and you
know there's there's reasonable tool
chains available now so i
this was from the implementation i did
in javascript for a previous stream but
um the instruction sets nice and compact
and still learnable you know like you
can reason about
the idea is to reason about what's going
on and still it scales
is that web app you're using in node i'm
assuming no it's in python
uh i wrote it um it's actually open
source it's
needs a lot of work but you know i wrote
it for this for these sessions
so that we could get coding and see the
same screen there was
not a lot of stuff that was available
that was like didn't have like licensing
or sign ups or
guilt wear or whatever i would argue if
you get into free diving
don't get thrown into the deep end of
the sea if you survive you survive
you should start in the swimming pool
yeah i mean i kind of agree to hair
studios and i think that's a
nice approach it's coming from something
like python 2c as opposed to like doing
c and then going to python
x you don't want my take on finally yeah
we can get into that during uh
we'll have some bourbon before we get
into that yeah i'll eat a glass of
scotch all right um
let's let's finish up let's do our free
real quick i was thinking about the free
i was gonna have one reach task which
was because you're free is basically
free
i was waiting to do it um no i didn't i
just thought it up um
but free because you're free was way
different like if there's
relatively nothing in the implementation
i thought it would be more fun
for us so you were asking about
malloc and how do i know if i allocated
memory or not and so i thought it'd be
really interesting to
add exactly what you asked for which is
like how can we trace allocations
because when we have our own allocator
we can actually
what do you mean by i'm sorry trace
allocations well we can tell whether you
gave back all the member remember before
the first time you used malloc you
leaked memory and it didn't tell you
right because there was no crash there
it just you know the
process shut down and everything was
fine and i said yeah you had your first
memory leak
well with your own allocator and even
some professional allocators you can
actually trace allocations you can say
like did i give back all of the memory
that i
allocated and one way we can do that is
if we implement free
not actually returning the memory but we
just keep track of the statistics
so let's for right now let's start with
our implementation of free so what's the
interface of free
i don't know well free and
what does it have to free i mean so i'm
guessing it's it's going to be another
void
yep it doesn't return anything and no it
doesn't return anything
it doesn't nope so what's free's job
what does free do
i mean i thought things always have to
return things and see nope
but i thought that's what we learned is
that when you're defining a function it
always has to return something yeah
the return type can be void which was
our first use of the word void
okay um which is a it always has to have
a specifier but
the specifier could be i'm not returning
anything
okay so this takes um
[Music]
the stick's size right
here engraved chunk on a barrel
anyway
a lot of professional mallocs will allow
you to trace there's a bunch of tools
but
you know it's such a wonderful trick
jess is building her own
allocator here so she can trace her own
allocations
okay um i look hooks i haven't learned
mellow cooks okay
um so
all right um
okay what does free chunk have to do
like what's its job uh um okay
so it needs to keep track of oh well
first of all you have the signature
wrong because
free is not it doesn't take a size
well in this case it we don't we're
actually not freeing anything so
actually what
no no but the interface is that you have
to tell it what it's going to free
the fact that we don't free it is an
implementation detail
wait sorry can you repeat that so
it's it's 10 pm my brain is like no no
it's fine the fact that our allocator
doesn't actually
reuse the memory is invisible to the
user
of this allocator right that's that's a
detail for chunk
and chunk people and team chunk and
that's it like it's not a detail that's
used by anybody who uses this library
so they think that this thing is going
to reuse the memory and later on if we
want to implement it to reuse the memory
we can but we have to keep the same
interface we don't get to change the
interface
team chunk man represent
okay um all right so what would it
regardless the implementation detail
that we're not giving the memory back
what would it need to know
i feel like it would need to know size
but it would also need to know
the pointer to like the starting place
that's what the free man page says
well good for the free man free man page
let's give it the
pointer to but it could be it could be
any kind of pointers i
will it's no it's going to be a void
pointer so that'll tell you right now
this is
this new i'm not this is straight out of
the man page
um
can't change the face i no
but how does it know how much to free
them
party time party time
that's up to you
wait no no no but but seriously like
terrible stroke if
i ask for like 500 500 like
like chunk units and it gives me that
and then i free that
how does it know that it's supposed to
free like 500 and not like 10.
hold on first three entire opportunities
please
os by the way please observe
workplace safety with whatever you're
engraving and playing with tools like
uh don't don't don't you might laugh in
this stream okay so
don't don't lose a finger or anything
because of what we're doing here today
so please
either put the engraving down and just
code with us
or please be great on everything i'm in
support of this
okay um but no in all seriousness though
how how does it know how much memory to
free
how could it no this is the interface
you don't get to change the interface
[Music]
you've said that and i get that but i'm
also asking then
if all it takes is a pointer presumably
the one from the allocator
how does it know how much memory to free
it only has an address how could it know
i don't know no i mean i'm asking how do
we how do we answer your question i mean
you're the one who wrote
malloc chunk malloc
chunk alloc
other than somehow recording like yes
you would have had to do the bookkeeping
no but but that requires a yes
like like i don't even know i we there's
apparently not see
dictionaries but that would have
something like that i warned you up
front
i wonder up front this is this you are
going to need some memory for
bookkeeping
i don't know why can't it just take size
it can i no that's i don't
you can't argue with the man page it's
the man page i can argue with whatever i
want to argue
okay um i'm a millennial
okay no but in all seriousness though
right um you wanted to learn c
that seems so no that's the interface
that that
the idea here is that you are so by
adding size that's something that you
want to know
because in this routine you want to
build it so that it doesn't need to have
any other
like information right okay
but and i get that that's a constraint
i'm just no no no no
but think about that no no that's what
you want
as the implementer right you want that
as the implementer but
who is going to use your implementation
and do they want to do that
are they going to want to track the size
as well it's going to use chunk alloc
i'm using chunk alok so i'm making it
for me
and you're always going to want to do
that even when the standard c library
doesn't require
it i mean who which which these
implementations is gonna win
i mean so with the other one though i
feel like it would be
so much faster to your point about speed
earlier
to not have to record every single like
size and memory address that i've ever
like allocated in this particular
instance
okay but now you're making a new
interface like because you're changing
the interface of free
no i i understand i can't do that but
i'm also saying like it's going to be so
much slower to have to record all of
this information
it's definitely going to add a little
bit of performance i mean making it fast
again we're aiming for correctness and
see eric has a perfect point
okay one is usability the other has
chonk
that's i'll use chunk okay you might you
might win on just chunk but
um the reality is that's an
implementation detail that most
developers are not going to care to
track
and because they're just not going to
use your libraries the reality and
that's how a lot of this stuff got
chosen in the first place it's like okay
this one was easier to use than that one
so i ended up using this one like that
technology won
like why did this seem to love to like
everything to be like
laboriously detailed and like have
control over it but they do
exact control over what they do have
that right if they want to build their
own memory allocator they can
just like you're doing right now i mean
they have exactly that choice
so this was about like what was a
reasonable like standard option
you know that people wanted to use oh
and see you later dutch caffeine thanks
for dropping by
because we also haven't really i guess
it would have to be an array
but like we haven't really learned if
there's any kind of like
dictionary-esque
sort of like keys and uh
value association data type and
yeah i guess we could make a structure
but like we could
wait but before you get into the
implementation that right now your free
chunk doesn't have to
what does it have to do based on our
initial constraints
well based on the because we don't
really need something to actually free
the memory we just want to you said
something about like keeping statistics
okay so before we add the keeping
statistics constraint
here's your implementation i'm going to
write your implementation of free chunk
i thought this was one that you wanted
to write but
i'm going to write it for you you ready
mm-hmm
done what
that's a trick maybe it's a trick
you said that we needed to like keep
track of statistics no that's what we
were adding on later but in the original
version we
that that's just to make it more fun is
we're going to add statistics but
to meet the interface requirements what
do we do
we really need it right yeah we don't
need statistics are not part of the
yeah interface requirements that's part
of our like you know that's a
reach goal but our actual implementation
that's it
okay this feels like
this feels like one of those physics
problems you want to test the free chunk
i don't know let's see if it works
okay first of all you didn't add the you
don't have the exact interface so i'll
take some points off for that but
this is the i keep swapping them still
in my head
um uh but be careful about that is
rigged because
we don't know that the user didn't write
a zero in there
so we we can't use zero we can't use a
pill
to signify that that is the end of the
allocation it's like her the intuition
she's going on is right that
you would need to trace the allocation
in some fashion
or you would need to i mean if you don't
want to use a separate structure you
could actually just
arrange your data structure so that
there's always like some bookkeeping
plus the memory plus some bookkeeping
plus the memory and so on so on
it would be nice with a map as trophy
i'm sort of mentioning but we don't get
a map in default c
oh or was adding on destroy i'm sorry
about that there's like i missed that
i'm a little behind in chat
i think i'm watching the stream thanks
harris for dropping by
you know here i thought we went through
the hard part with the malloc and we'd
do the nice easy part that'd be a nice
gimme but
he just didn't want the gimme
[Applause]
[Laughter]
and yes nathaniel's right um strophium's
right a map would be ideal we don't have
a map
so we don't get that in default c so
what do you mean by a map i'm sorry a
map is that is that a data type in c
no it this is you you get this it's a
dick in python okay it's
it's a dictionary yeah yeah all right it
that's an
unordered map as opposed to a order it
depends which language you know
map is an overloaded word um using the
java definition it's really just an
interface and the it could be a hash map
underneath it could be an array map
maybe whatever you know it's just
one of those things um but yeah moral of
the story is that
it's key value it's somehow related it
doesn't talk a map
is non sp when you use the word map
you're being non-specific about the
implementation which is
what i like so harry studios has a
really good question and i know we're
learning c not c
plus plus but like for a buffer that you
call delete
how does it know how big the buffer is c
plus plus is
not this stream that's an interesting
question right like to learn
well here's how c does it but also
here's how other languages tackle this
i'm interested first in how jess does it
because you know
we haven't gotten to europe apparently
i'm cheating it's just like an
empty year i'm telling you that's what i
was telling you earlier because i'm
going to make choco s
beautiful