In this video we're going to talk
about how well parts of a function work together.
If one function does two completely different things,
then the rate of cohesion is low.
If the all parts of
the function work towards a common goal,
one thing, then the cohesion is high.
If the cohesion is low it's better to
break it into two separate functions that
just makes things simpler and
cleaner conceptually and programmatically.
So what we're going to do now is
define some new interfaces.
You'll notice that on the next slide we have
the create queue and the delete queue separated,
that avoids the entire flight problem.
You want to create a queue, call create queue,
you want to delete it, call delete queue.
You're not going to call delete queue with
the understanding you're going to create the queue, why?
Well, for one thing it requires a token,
the Qticket belonging to an existing queue,
and If you send it anything
invalid, it's going to object.
Same with create queue,
it doesn't take any arguments.
Therefore, you're not going to pass in
an argument with the thought that you'll delete it.
Then we've got put on queue and take off queue.
Put on queue is basically the same thing we had
before in the fragile library.
But notice the poll number
off the queue, the take off queue.
We're not passing the address
of an integer to put the number in,
we're going to return the number.
The reason for that is we have no way of checking
that integer pointer actually points to an integer.
All we can do is check to see if it's null.
So what we're going to do here is return it as I said,
but then we have a problem,
how do we disambiguate between
int and an error code
if what we're returning is negative?
We'll talk about that in a few minutes.
Okay. Now, let's take a look at the queue structure.
This is completely invisible to the column.
Therefore, if we decide to change it in any way,
it's not going to affect
anything done in the calling program,
it only affects the internals of this library.
Again, like you did with queue air buff,
I'm going to make one concession to exposition.
I'm going to assume that there is
a maximum number of elements in the queue,
and a maximum number queues.
Again, we could easily do this using
malloc so that we wouldn't have this issue of limiting.
But for exposition, I wanted to keep it
relatively simple which is why I left those off.
It'd be a good exercise to try to
rewrite this where you don't have those limits.
Anyway, we've got worse
making the elements of the queue b integers as before,
but now look at the structure,
we've had in count is the same.
Now we have queue of an array of integers,
and we can have up to max elt integers.
Then, we have the ticket itself
that you can think of as the unique queue ID.
We have an array of MAXQ queues,
so there's a limit on how many queues you can define.
We also have a nonce,
and we're going to begin that an nonce at someplace.
In this one it was 0x0502,
if I remember correctly.
The point is that number is going
to continue to increase.
So now let's look at generating a token,
and this is where you're going to see some paranoia.
This is only going to be called within the library,
so it's a private function,
and in C, the way we do that is we declare it static.
So it's not visible to anything outside the file.
In C++, you private
it to make sure it's within the module.
We have two internal variables,
high for the index and low for the nonce,
and we're passing in the index of
the queue that we want to generate a token for.
So what's the first thing we do?
Well, we check to make sure that the index is valid.
If the index is too big,
we immediately return an error and
this is an internal inconsistency
because the index should never go
beyond the maximum number of queues allowed.
The next slide tells you about function hiding.
Okay. So once we've checked that the index is valid,
we need to generate the ticket.
So the first thing we do is since we've met most 16-bits,
we want to make sure that whatever we
generate is going to fit in those 16 bits.
So first we generate the index plus I
offset and make it 16 bits long.
Notice, we're clobbering the high-order bits,
so it's actually 15 bits,
we want it positive.
We then check to be sure that the number after taking
the low 15 bits is the same as the index plus I offset.
If that's false, that means we hit an overflow,
and so we want to give an error message
basically saying, "Hey, it's too big."
Again, this is an eternal error that should never arise.
Assuming it doesn't arise,
we now have the first part,
the high part of the ticket.
So now we do the low part which is the nonce.
The nonce we just locate for 16 bits, we don't care.
It's unsigned, so it doesn't matter whether it's
positive or negative, it's always positive.
We then check to be sure that again
the nonce is no more than 16 bits long,
that it didn't suddenly go beyond 16 bits,
and also we want to prevent it from being zero.
If either other of those happen,
then we have an error and we return it,
otherwise we simply construct a return the ticket.
So now the ticket contains the index
plus an OFFSET in the high-order 16 bits,
and the non-explicit OFFSET on the low-order 16 bits,
and it gets passed back to the column.
Now, two things about this routine.
The first one is that if
you go back to the token generation slide,
we used x7fff instead of xfff as we did with the nonce.
Why, why don't just use all 16 bits?
The reason is this,
if this is a valid token,
we will want to return it to the user.
If it's negative, if you
have that extra f, if you have ffff,
it's possible that high-order bit would be set,
which means it would be set in the token that's returned
which means it will be seen as
negative and therefore an error.
So we always want the token to be positive.
But we really don't care about the nonce,
because the nonce is in the low part,
so you never going to look at the sign of the nonce.
In fact that's why it's declared unsigned.
The next slide asks these questions.
So this brings up a checklist,
and what I'm going to do as we go
through this is gives you
checklists of things that we learn as we go along.
The first thing is to make the interfaces
simple even when only for internal use.
That way you're less likely to make a mistake, and yes,
programmers who program these things
including me and you can make mistakes.
The second thing is to check everything
even internally generated parameters
because you never know when a change might
affect the parameters that you generate.
The third thing is be helpful,
give useful error messages whenever you can.
That will help whoever is using it, calling it,
or debugging it to figure out what went
wrong and if they should need to call someone else.
Now that we've generated the token,
what happens when the tokens returned?
Well, we need to interpret it,
and that's what we do here.
The first thing we do in this routine read ref in
the token interpretation slide
is simply get the token as a parameter,
and then we compute the index number
and check it for validity,
to make sure that it's valid.
If it is not valid, we give an error message,
but this time it's not an internal inconsistency because
this routine even though it's internal
only was part of something the caller gave us.
So we return a bad ticket message.
Assuming the index is valid,
we then check to see if there's
actually something allocated to it.
If there isn't, then
again that's a bad ticket because it's referring
to a queue that was never
created or that was created and later deleted.
Okay. Assuming neither of those truly have valid index,
there's a queue in that in the element of
the queue array for that index.
But the question is, is that the right queue,
in other words is that the queue belonging to
the ticket that was passed in or to a later ticket?
That can arise when someone deletes
a queue and then the slot gets re-used.
So that's what we check here.
We simply check to be sure
that the ticket that is stored in
the queue structure corresponds
to the ticket that was passed in.
The high part will match because of what we did earlier,
the checking, but the low part
may not if the nonce is different.
So that's where this would cause an error,
and again if there's a problem
where you return bad ticket.
Okay. Now we've got a valid queue and a valid index,
but the next question is did something mess up,
did one of the internal parameters get messed up?
So the first thing we do is we check to be sure that
the head index points to a valid location
in the queue array and that the count is
also greater than also at least
zero and no more than
the maximum number of elements that can be stored.
If either of those is true,
then there's an internal inconsistency
and we immediately stop.
We then take a look at the ticket and
check that the nonce is not zero.
If the nonce is zero, something went wrong
and that's another internal inconsistency.
Assuming it passes all those two checks
or all those checks,
we then simply return the index to the caller.
Now in C, there's a very nice macro called assert.
Assert allows you to check for error conditions.
If the error condition holds,
in other word certain condition fails to hold,
it'll immediately exit the program.
So for example, at the top there where I was
doing all the checks for head and so forth,
I could have written that assert
queue index arrowhead is less than zero,
then another statement assert queue arrowhead
is greater than or equal to max out and so forth.
Which approach is better?
The one I used to give the error
messages or using assert?
The answer is it depends,
pretty much everything in
security here is than the answer.
In general, it's better to let
the caller worry about the problem.
So you simply do what I didn't
pass the information back to the column,
and then the caller can decide whether or not to dumb,
to crash, to stop the program or whatever.
However, in some cases,
it may be better to have the library
stop the program especially
if it's a system critical function,
and in that case you would use the asserts.
So again, we have a checklist here.
Now, notice how we designed the token,
we've designed it in such way can be checked for
validity, and we do that.
We also assume that the references,
in particular the token may refer to old data.
We don't trust the token to
always refer to the newest thing,
so we have the nonce to do the checking.
The last thing is in general we've been debugging checks.
Yes. This makes your code bigger,
but when something goes wrong,
you'll be very thankful.
If you cannot leave in the debugging code
because for example you're working in
an embedded system and space is critical,
then what you should do is not delete it but
commented out or use macros,
If deaf debug and if, something like that.
That way if something does go wrong,
you can immediately turn on the debugging statements
and run the program with
the suspect input or other suspect input.
So in general, it's better to leave
the checks in than to remove them.