Based on my campus, this is a really busy, stressful time of year. So you've taken an hour for bonus math outside of what you have to do for class. I think that's pretty great. I really like giving this talk because I think the title is something all of you can relate to. I mean, there's no scary math words in this title, right? But when I say what's in your wallet, this is not a credit card commercial. I'm guessing you probably have a student ID. You might have lots of other things in your wallet. What I want to talk about today is coins. Again, something all of you have dealt with, right? Pennies, nickels, dimes, and quarters. You might be wondering how we're going to get a whole 45-minute talk out of this. Because surely you spent lots of time adding up coins maybe in grade school. You think it's all done. But I hope to convince you in the next 45 minutes that if you look at them the right way, there's actually a lot of interesting math hiding inside of here. But the first issue is not everybody spends their coins in the same way and so you can see my menu across the top here. I've come up with a few models of how I think people might spend their coins. And we'll talk about the mathematics that goes with each of those models of how people spend their money. So are you ready? I'll also say one more thing I tell all my classes on the first day. I show up for conversations. I think dialogues are more interesting than monologues. So if I ask a question, I hope even though we're just meeting just now, you're willing to tell me what you think. So don't be scared if I ask a question. That's my other disclaimer. But my first model is what I think is the simplest way to deal with coins. It's what my brother does. Do you have any guess what I might mean by coinkeeper? Sure. Piggy banks. Piggy banks, yeah. And it doesn't even have to be a piggy bank, right? It's someone who hangs on to their coins. My brother really doesn't like having coins in his wallet. And so when he has to spend cash, he pays in bills. And then sometimes he gets coins as change.   And you put them in a piggy bank or in a jar if you're not quite as fancy. Here's my question to you. What percentage of the coins in the jar do you think are pennies? Any guesses? If you say something between 0 and 100, you're doing all right, because that's a percentage, right? We heard 90, we heard 50. I guess the majority. Over 50%. So we're thinking a lot of pennies. Do you have a reason for that, or it's kind of your gut feeling? Majority of the time is 2 cents, 90 months, and if you remove a penny, you screw up the whole system. OK, that's true. Pennies are involved in a lot more transactions than transactions that only take silver coins. So yeah, we'd expect a lot of pennies. Have I given you enough information to answer this question? Or do you maybe have a question for me? I heard something. Well, how many pennies? That would help me answer the percentage if I knew how many pennies and how many are in the whole thing, right? But I think I also need to tell you about my assumptions on how the pennies get in the jar. So here are some assumptions I'm going to use throughout this talk. First, I need some assumptions on what prices look like. And you can tell me if you think this is reasonable or not. I know you might look at this and say, a lot of prices end in 99 cents or 97 cents, so maybe I'm making things too simple. But here's my counter argument. When I go to the grocery store, I don't just buy one thing. I buy 10 or 15 or 20 things. And by the time I buy a whole group of things, I really can't predict what the coin part of my grocery receipt is going to look like as reliably as I can that a can of soup that probably ends in 99 cents. So if I'm buying a collection of things, I think this is a little more reasonable. And if you don't think it's reasonable, well, my homework to you is rewrite the talk with a new assumption for number one. Because this is the assumption I'm going to use to keep things simple for this talk. Number two, I think, is a little less controversial. I'm going to assume that when you spend money, the cashier gives you change in a predictable way. And even if you don't have math words for this predictable way, I think you know what I mean. So let me check my conjecture. If the cashier needs to give you 4 cents, what coins do you expect them to give you? 4 pennies, because that's the only choice, right? What if the cashier needs to give you 6 cents? What do you expect them to do? OK, but that wasn't your only choice. Why are they doing a nickel and penny instead of all pennies? Less change, right? So they're trying to be efficient. What about 41 cents? What do you expect? OK, one of each. If we're only dealing with pennies, nickels, dimes, and quarters, 41 cents is one of each. But that was one of 31 choices. So does the cashier have to think through all the possible ways to make 41 cents? Or is there a quick way for the cashier to make change? What do you think? What's that? I heard something in this direction. You could do four dimes, one penny. That's one option. But my guess is the cashier would probably do this, because this has five coins and this has four. So in my experience, the cashier gives me the fewest coins possible to make change. But do they really have to think through this whole list? I don't think so. I think they're actually doing something that's called the greedy algorithm. And so that might sound a little bit more like math words, but don't be scared by the inequalities here. What this says is if the cashier needs to give you C cents, they're going to give you as many quarters as possible without going over. Then they're going to look at C minus how much they gave you in quarters and give you as many dimes as possible. And after they're done with quarters and dimes, as many nickels and then as many pennies, so there is a quick way that cashiers often make change. And let's check that this setup makes sense with 47 cents. How many quarters would a cashier give you for 47 cents? One, right, because two is too many. It would go over 47. So now you have a quarter. How many dimes would they give you? Two, right? And now you're up to how many cents? 45, OK, still not so scary on the math, right? How many nickels? Zero, because if I gave you a nickel, I'd go over. And then how many pennies? Two, and pennies are the cleanup job. So this is called the greedy algorithm, where I give you as many large-valued coins as possible first. And then I just go down in size of coins, quarters, then dimes, then nickels, then pennies. But is this really the most efficient way to make change? Is this something you know? Or is this something you trust that this process will give you the least possible coins? Trust? I'm glad you're willing to admit that there's some thought that goes in here. Because let me take you to a different world for a minute and then come back to this. I don't think it's always obvious the greedy algorithm is the most efficient way to make change. For example, what if you only had 1 cent, 3 cent, and 4 cent coins to work with? What does the greedy algorithm say you should do to get 6 cents? Start with a 4, and then after the 4, what do you do? Two 1s. So the greedy algorithm will give you three coins to make 6 cents. Is that the best way in this world? What's better? Two 3s. So there are systems of coins where the greedy algorithm is not the most efficient thing. And people actually do research on this. Look at the year on this paper. I see everybody in here looks more than 12. So this is in your lifetime. This is a paper on you can input the set of coins you have available, and it will do a computation and say either greedy algorithm is the best thing to do or no, there are times like this where the greedy algorithm is not the best. So people actually think about these things. The change making problem is a research problem people talk about. And I'll tell you often the greedy algorithm is best. And in the world you live in with pennies, nickels, dimes, and quarters, it is. But it's not a trivial, obvious thing to say the greedy algorithm is always the best thing to do. So I've taken a little bit of a detour to tell you about my assumptions. Do you remember my original question? OK, you're all with me. This is awesome. So I want to talk about my brother's coin jar. And this was all a detour to be clear on my assumptions. If I'm assuming that all the prices happen equally often, if I want to get a snapshot of what's in that jar, I just need to think of one copy of each of these 100 transactions. And then I can tally up the coins. And that's the distribution of pennies, nickels, dimes, and quarters I expect to see in the long run in this jar. And well, if I'm charged $1, I know I'm getting nothing in change. But I can go through each of these transactions and say, what would the greedy algorithm give me? For example, if you got charged $0.76, you'd expect $0.24 in change. And this is how you'd expect it. And I don't want to make a list of 100 things, but my computer does it for me. And it says the total coins I have after all these 100 transactions are right here. And so there are more pennies than anything else, but it's actually slightly under half, interestingly enough. So this is the distribution I expect to have in my brother's coin jar. And this talk is actually based on a paper I wrote with a friend when we were writing it every so often I'd call my brother and say, tell me the percentage of coins you have. And this was actually a pretty good model for what he finds on his coin jar from time to time. So that's my first model, the coin keeper. Any comments or questions before I switch it up a little bit? That was my assumption at the very beginning. Remember if I go back here? And so yes, according to going way back here. That was my first assumption. So matching this assumption, that's what's going on. So if you think you have a better model for how the prices are, then you're welcome to redo this computation with a different assumption. But yes, for the sake of this talk, you correctly said the assumption I'm using. And I gave you my motivation for that. We usually don't buy things one at a time. We usually buy them in groups. And then that does even it out quite a bit. So good observation. And realize that's going to stick with me the rest of this talk to stay consistent. So yeah, if you don't think that's what models the prices you're spending, this is not quite the right computation. But assuming they're all equally likely, yeah, that's what you would get. And so now I'm going to show you a different way where you don't just collect coins, but you actually spend them. But I'll start simple with that too. And I'm just calling it the simple spender. So my friend Eric that I did this project with really hates spending cash money at all. And so he uses his debit card as much as possible. But there's one exception. The coffee shop down the street from his office doesn't take debit cards. So he has to pay cash then. And so the only time he spends cash is when he goes to get his latte. And his latte costs $5.20. And he doesn't like carrying coins. So if he has no coins, he's going to have to do like my brother and spend dollar bills and get some coins back and change. But he doesn't just take the coins home. The next time he goes to the coffee shop, he tries to get rid of some of his coins. So let's think about what Eric's wallet looks like. If he doesn't like coins, he starts out with no coins. After he buys his first latte, how many coins do you expect him to have? How many cents? 80, right? That's your change from $5.20. And now he goes and buys another latte. How much do you expect him to have? 60, because he can do the bills on the side. And then he can spend $0.20 of his $0.80 to work on getting rid of them. What happens after 60? 40, and then back to start. So Eric's wallet kind of moves in a cycle. If you know how much money is in his wallet right now, you have a 100% chance of knowing what it's going to be after his next transaction. And it only takes one slide to analyze Eric's wallet. But I want you to be on the lookout for this kind of behavior as we move through some more complicated models. This is what I'd call cyclic behavior, where when you know what you have at one point, there is a 100% chance of where you're going for the next transaction. Does that definition of cyclic behavior make sense? All right. Well, then we're going to go to something a little fancier. In fact, we're going to go to another planet and talk about some coins that don't look like ours to work on building up to the whole big picture at the end. So we're going to go to a planet I call Markovia. And their coins look kind of like Skittles. They come in two colors. They're kind of high tech. So in Markovia, they're not using these coins for spending money. They're using them for playing the lottery. And their lottery is a little bit weird. So let me explain the details, and then we'll just have the summary version on the next slide. When you go to play the lottery, you go and buy one of these Skittle looking tokens. And it comes all wrapped up, and you open it, and there's a 50-50 chance that it's red versus that it's blue. And then to keep the drama up, they have 10 rounds of the lottery. So in each round of the lottery, your Skittle looking coin might stay the same, or it might change color. And then after 10 rounds of this, everybody who has a blue coin shares the prize of the end. And so we're going to analyze these red and blue coins. Again, this is my shorthand. So this first row says, at the beginning, there's a one-half probability of having a red coin, one-half of having blue. And then these other two rows tell me the probability of changing from one color to the next in one round of the lottery. So starting red and staying red has a 2-thirds chance. Starting red and changing to blue has 1-third. And then similarly down here. Does it make sense how to read my table? OK, so instead of all these words, I'm just saving the table on the next slide. This is the main information you need to know about this lottery. And to check that these probabilities make sense, I have some questions for you. So if I have a blue coin now, what's the probability that it's going to switch red in the next round and then blue right after that? Any thoughts? I could take half the question. If I have a blue coin now, what's the probability it'll be red in the next round? So if I have a blue coin now, the probability it's red in the next round is 3-fourths. And then I said after that it changes from red to blue. What's the probability of changing from red to blue? 1-third, what should I do with those two numbers? Multiply them, because I want one thing to happen and the other thing to happen. When you want two things both to happen, you need to multiply 1-third times 3-fourths on a good day as 1-fourth. There is a 1-fourth chance of having blue, then red, then blue in subsequent rounds of the lottery. Are you with me? Let's get a little more fun, because that still doesn't tell me if I win. What's the probability you have a completely undramatic coin that when you first get it, it's blue, and it stays blue for the whole lottery? Any thoughts on how I'd compute that? OK, 1 over 4 to the 10th tells me blue to blue. That's most of it. What else do I need besides that it goes blue to blue at each of the 10 rounds? Yeah, yeah. So it'll be combining those two. I need to start with having a blue coin. That's what that 1-half is. And then for each of these 10 rounds where my coin may change color, I need to multiply by 1-fourth, because that's the probability of having blue and staying blue. So 1 over a little more than 2 million, not very likely that you have an undramatic coin. There's a bit of hype going on here. Do you understand where these probabilities are coming from? I still haven't answered the big question yet, though. If you're playing the lottery, you don't care if you have an undramatic coin. It could be red, blue, red, blue, red, blue, as long as it ends on blue. That was the rules of this crazy lottery. So what's the probability you actually share the prize at the end of 10 rounds? I think this is at least a little more complicated. You can agree on that, right? In fact, the answer is we need to talk a little bit about this model called a Markov chain. So a Markov chain is a model for exactly this kind of situation where you have a finite list of things that could happen. The only things that can happen here are I have a red coin or I have a blue coin, only two possibilities. And the only probabilities, the only way that events are related are going from one time step to the next. So the probability I have a blue coin now just depends on what color I had one round ago. Doesn't matter what color you had five rounds ago. The probabilities all go from one time step to the next. And it turns out to answer this question, it's going to help if I stop writing a table and break this up into two matrices. Because do you see there's really two kinds of probabilities running around in this table? In the first row, these are probabilities about what color coin you have at just one instant in time. And these four are really transition probabilities about going from one step in time to the next. So I'm going to break these up into two matrices. That first matrix I'll call a vector because it's just one row. You see in red the probability of starting with a red coin. And in blue the probability of starting with a blue coin. And then this square matrix tells me about my transitions. I've color coded them again. So this first row still stands for starting with a red coin. This is the probability of going from red to red. This is the probability of going from red to blue. And similarly on the next line. Exact same stuff that was in your table. But now I've put it into matrices because it's two kinds of probabilities. And I claim if you want to know what's going on, I steps into the lottery. You really just need to take that initial vector and multiply it times this two by two matrix I times. So to convince you of that, let's see if we can remember how to multiply two matrices. I have a one by two matrix times a two by two. How big of a matrix should I get when I multiply those? One by two. Okay, so that's a good size if I'm looking for a snapshot of red versus blue at one moment in time. And think about how you actually multiply these to get my one by two matrix. The first entry is gonna be this row times this column. So you notice the one half times two thirds is there. The blue one half times the three fourths is there. And to get this second entry, I'm gonna take that vector times this column. And so same idea. You see the red one half times the blue one third. You see the blue one half times the blue one fourth. And I hope these colors convince you where these numbers are coming from. What are we computing here? This is starting red and staying red or starting blue and changing to red. These are the two ways to have a red coin one step into the problem. Did that make sense? I see some nodding. I see no one looking angry, so that's a good sign. Over here, what does this represent? Okay, starting red changing to blue and what does this represent? Starting blue, staying blue. So these are the two ways to have a blue coin one step into the problem. And so one step into the problem, there's a 17 24th chance of having a red coin and a 7 24th chance of having a blue coin. How would I figure out the probabilities two steps in? Do it again. That's right. If I wanna go one more step in time later, I'm gonna take this times this matrix. And sparing new details, that's two steps. And if you wanted to go 10 steps in, what would you do? Yeah, keep multiplying by P one more time for each round of the lottery you wanna do 10 steps in. There's a 30.77% chance that you get to win the Markovian lottery, pretty generous lottery. But it's a good model for trying to follow what's going on with all this matrix multiplication. And you remember what I called this whole setup here? It's called a Markov chain, right? Markov is somebody's name. I wanna tell you a little bit more about Markov chains. So there's a few kinds of Markov chains and it's really important that we understand which kind we have before we move forward going back to our forward and back before we go back to our original set of American coins. So here are some of the things that can happen in Markov chains. Think about this lottery and do you think each one of these applies or doesn't apply? So one kind of Markov chain behavior to look out for is absorbing states. Remember our states here are you have a red coin or you have a blue coin. An absorbing state is a state where once you get to that state, you're stuck there for forever. Does our Markov chain have any absorbing states? Okay, no. If you have a red coin, there's always a chance it could be red or blue on the next round. If you have a blue coin, there's always a chance it could change on the next round. So we don't have absorbing states. A practical example of an absorbing state might be if your high school tracks whether students are freshmen, sophomore, juniors, seniors, what happens after senior? Yeah, hopefully you graduate and if they still keep track of their alums, right? Graduated is an absorbing state because once you've graduated, you're not gonna go back to those other states. So that's not a coin example, but we wanna look out for those. Our lottery does not have absorbing states. Ciclic behavior is when you have a bunch of states where you cycle predictably between them forever. Have we seen Ciclic behavior in this talk? Okay, where? Okay, the simple spender, my friend buying his latte, right? He had a very predictable, only one kind of time he spent his money and so his wallet went in a cycle. Does our lottery act in a cycle? Okay, no, you could go back and forth between red and blue, but it's not like if you have a red coin, there's 100% chance it'll be blue next and 100% chance it'll be red next. Cycle means when you're in one state, there's a 100% chance of knowing where you're going next. So ours isn't absorbing, it isn't Ciclic. If your Markov chain isn't absorbing and it isn't Ciclic, it's probably regular. So our Markovian lottery chain, lottery example is regular. Here's the math definition of regular. Do you remember what P stood for on the previous slide? Which matrix was that? It was the square one, right? That two by two one that told me my probability of what happens from one round to the next round. The official definition of a regular Markov chain is one where this transition matrix to some power has no zero entries. So what does that mean in practical terms? It means think of your favorite state in the Markov chain and think of your second favorite state in the Markov chain. If you wait long enough, there's a non-zero chance you'll get from point A to point B. That's what that means. If you wait at least n steps, you can get anywhere in the Markov chain. So our Markov chain for this lottery is not absorbing, it's not Ciclic, it's regular, which means I actually know a strategy for figuring out what would happen if we kept playing this lottery instead of 10 rounds, but for forever. So let me tell you how to figure out what's really going on in the long run in this lottery because it's regular. Here's the idea. If you have a regular Markov chain, in the end it's gonna settle into this long-term probability distribution of here's the percentage of the time I have a red coin and here's the percentage of time I have a blue coin. It's gonna stop wavering around and kind of approach a limit. And so if you have this vector of probability of having a red coin and then probability of having a blue coin and it really is the long-term distribution, when you multiply times this transition matrix, you should get back the same thing. That's what long-term distribution means. And so if I wanna figure out what would happen from playing this Markovian lottery for forever, well I really need to do that vector of probability of being red, probability of being blue times my transition matrix equals that vector again. And so notice these equations are what I get from multiplying these two matrices. Do you have an idea where this last one comes from? Yeah, yeah, has to equal one, that's right. So this whole list of numbers in L, there are a bunch of probabilities that run through all the possible states. The sum of those probabilities has to be one. And so I can solve this system of equations and it says if you play the Markovian lottery for forever, there's a 913th chance of having a red coin and there's a 413th chance of having a blue coin. So this strategy right here of finding the long-term probability is the strategy I'm gonna use moving forward. I just always have to check that my Markov chain is regular before I try this strategy. So now I'm ready to go back to real coins. We went to Markovia so that we had an example that we could see really well. But do you have any questions about this example before I go back to US coins? Yeah. So yes. So whenever you have one of these transition probability matrices, what's the sum of each row here? One, right? And so as a consequence of that, the last equation I write here is always going to be dependent on previous things. And so you do need this. Yeah, that's gonna scale it down to actually be probability size. So yeah, it looks like I have one too many equations, but as a consequence of this being a row of probabilities summing to one, the last one that came from here is unnecessary. Good question. Other questions or keep going. Because we still gotta get back to those coins at the beginning of the talk, right? I don't think we're quite ready for all of them though. So let's start with a slightly simpler example. Let's pretend we live in a world that just has quarters and 50 cent pieces and all our prices end in multiples of 25. What are some possible collections of coins you could have in your wallet in this world? Okay, if you're really poor, how many coins are in your wallet? Okay, could have zero. What's another collection of coins you could have in your wallet? Okay, you could have 25 cents. What else could you have? 50, how many ways are there to have 50 cents? Two. And there are two ways to have 75 cents. And if you're determined to spend your money, you're never gonna have more than this. Because if I get to here and I'm charged some amount of money, I'm gonna spend and get rid of some of it. So this is an example that instead of two states has six states, and I can play the same game as I did for the Markovian lottery and set up this transition matrix. So here my rows and my columns are labeled in this order. Let me talk through, for example, the first row here. So this first row is your probabilities from starting with an empty wallet and then ending with empty or 25 cents or 50 cents and so on. Do you understand why the entries are all zero or 1 fourth? Why 1 fourth? What was my first assumption in this talk? I'm assuming what about the prices? Yeah, that they're equally distributed. And so there are four possible charges I could have, zero cents, 25 cents, 50 cents, or 75 cents. And I'm assuming that they're equally likely. So there's a 1 fourth chance of starting with an empty wallet, getting charged zero cents and staying with an empty wallet. There's a 1 fourth chance of starting with an empty wallet, getting charged 75 cents and then ending up with 25 cents and change. Let's see, this one is starting with an empty wallet, getting charged 50 cents and then getting a 50 cent piece efficiently and change. And then this one over here is starting with an empty wallet, getting charged a quarter and then getting this in change. And so you won't get to here or here in one step from the empty wallet but there's a 1 fourth chance of going to any of these four because we were assuming the prices are distributed uniformly. I could talk through another row if that helps or you can say that makes sense go on. What's your feeling about this matrix? Okay, okay, so I sat there and I thought through all the options, right? Starting with an empty wallet, starting with 25 cents and so on. This is my transition matrix for this particular situation. And let's see, what kind of Markov chain am I hoping this is? What was the vocab word? Regular, regular means that no matter what two wallets states you're thinking of, if you wait long enough, there's a non-zero chance you'll get from point A to point B. I promise that if you take this matrix to the third power the zeros go away. So if you trust me, I've checked. This is a regular Markov chain and I can use my strategy. So I want this list of six probabilities of what's the probability of having an empty wallet? What's the probability of having just a quarter and so on in the long run? To find the long-term probability I'm really solving this equation. Well, there's six variables here. So I have six equations that came from the transition matrix. And again, this last one is all my probabilities gotta add to one. Again, no one wants to do that by hand, really. So I get my computer to do my work and it says this is the answer. One fourth of the time I expect an empty wallet. One fourth of the time I expect 25 cents. Does that surprise you or no? Why should I one fourth of the time have an empty wallet? Because what am I assuming? Yeah, I'm assuming the prices are evenly distributed which also means the amount of change in my wallet is evenly distributed between zero cents and 99 cents. And if there's only one way to have an empty wallet, one fourth of the time I'm gonna have an empty wallet. There's only one way to have 25 cents. So one fourth of the time I'm gonna be in this state. There were two ways to have 50 cents. So notice these add up to one fourth of the time but a 50 cent piece is a little more likely than two quarters. And I'm gonna have 75 cents one fourth of the time but apparently it's a lot more likely to have a 50 and a 25 instead of three quarters. So the machinery still works, it just got a little bit bigger than the Markovian lottery. Comments, questions, concerns, or scale it up because we're getting close to what I promised at the beginning but I wanna make sure you got the steps along the way. How are you feeling? Okay, I got some nodding, I got some thumbs up. You look happier than my calculus students on a Monday so that's good. So now you see my title, the whole shebang. We're gonna think about what happens if I use pennies, nickels, dimes and quarters. It's gonna be bigger than six by six. So first again, let me go over my assumptions. These are the ones I've had the whole time. Number one, I'm still assuming the fractional parts are distributed uniformly. You can either say that's an unrealistic assumption and rewrite the talk with a different number one or you can say okay, I get it if you buy things in groups. I'm assuming cashiers return change using the greedy algorithm but I also need some assumptions on how you're using your coins. So here are some assumptions I'm gonna make about how you spend your coins for this particular version of the model. So number one, if the coin part that you're being charged is more than the amount of coins in your wallet, you're just gonna sit on it and get change. So for example, if you have 25 cents and you get charged something that ends in 32, you'll say okay, whatever, I can afford to get more coins. But if you have more coins than the coin part of your price, I'm gonna assume you overpay by as little as possible. For example, if you were charged something 29 and you have 30 cents, you'll pay the 30 cents and then just have a penny in change. Did that make sense? But you don't have arbitrarily many coins to work with and so sometimes there might be ties. Like right, there's two ways to make 30 cents. Maybe you have a quarter and a nickel and you also have three dimes and so if you have to break ties, I'll assume that you go for the big coins first. You would rather spend a quarter and a nickel than three dimes and you can redo this where you change the assumptions but for the purpose of the example I'll show you, this is how I'm assuming you're spending your money. So the first thing we need to figure out is does this make sure that you never rack up infinitely much money? Like is there a maximum amount of coins you expect in your wallet? How much is the maximum you think might be in your wallet if you spend in this way? Okay, 99 cents and we can prove that. If you have 99 cents before a transaction at most, you'll still have at most 99 cents after, right?  So that's starting with 99 or less and ending with 99 or less. What if the price is more than what's in your wallet? Well, you're gonna stick with your money that's in your wallet and you'll get 100 minus P and change and notice I've just regrouped the parentheses but this is the same quantity. It's 100 minus a positive number so it's still less than 100. So yeah, it's true. There's a cap on how much is in your wallet with my assumptions, you have at most 99 cents. Before I set up a matrix, what kind of Markov chain am I hoping is going on here? Regular and regular again means no matter what wallet state you think of, wallet state A and no matter what wallet state you think of, wallet state B, if you wait long enough, there's a non-zero chance that you can get from A to B. I'm gonna give you a recipe to get from your favorite wallet state A to your second favorite wallet state B to convince you this is regular. This might not be the most efficient way, but it is a way. So let's say you're in wallet state A. You have your favorite wallet state in mind. Is there a way to get from there to the empty wallet? How much would you have to be charged to get from your favorite wallet state to the empty wallet? Yeah, exactly that amount. And since you have at most 99 cents, that's an option. So in one step, you can get from wallet state A to the empty wallet. And now I claim there's a smart sequence of charges that will get you from the empty wallet to whatever you thought of as wallet state B. Pretend you're trying to get to a wallet state that looks like this.  And since this wallet state is at most 99 cents, you're trying to get at most three quarters. That 75 cent charge is still always gonna be more than what you have in your wallet at the moment. So doing this first will rack up Q quarters. Then after you've racked up as many quarters as you were hoping for, you have at most 75 cents. So getting charged 90 cents, you're gonna sit on it and start racking up dimes and so on. This is a recipe that gets you from any wallet state you wanted to start with to the empty wallet and then from the empty wallet to this other one in at most Q plus D plus N plus P plus one steps. So it's regular. Didn't promise this was the most efficient route but no matter what collection of coins you have, less than 99 cents and whatever collection of coins less than 99 cents you were hoping to get to, there is a way to do it. This is regular so my plot I've been using will work. How big do you think the matrix is? We've seen a two by two and a six by six. How many states will there be if you're trying to model all the ways to have up to 99 cents? Any estimates before I show you? Thousands, like how many thousands? Okay. Does anyone wanna say high or lower? Exactly right. It's big. It's bigger than six. Do you have a reaction? Okay. 99. 99 total states? 99, it's a nine. Okay. A nine X. Yeah. I'll point out that you can have up to 99 cents but there's more than one way to make most of those so it's gonna be more than 99. In fact, if you have at most 99 cents, right? You have at most 99 pennies, at most 19 nickels and so on. If you just multiplied all the options for pennies, nickels, dimes and quarters, it'd be 80,000 but most of those are overkill, right? Cause if you have 99 cents already in pennies that forces you to have zero of the others. So again, I get my computer to do my work when I can. I had the computer go through all of these 80,000 possible states and say, yeah, that many survived and are less than or equal to 99 cents. So more than 5,000 but you're in the right ballpark. 6,720 rows, 6,720 columns and I'm not gonna actually write out all the digits but I'll zoom out and show you a picture of it. This is the zoomed out version of this matrix. The almost 7,000 rows, almost 7,000 columns. You can think of the white spaces entries that are zeros and then we were assuming the prices are evenly distributed so there's all those black dots stand for one over 100s. So there's 100, one over 100s in each row and a lot of zeros. And if you've had linear algebra already this next paragraph is for you, if you have not don't stress it won't matter on the next slide but I do wanna connect it to things people who have seen linear algebra before might recognize. This equation that we've been using all along should look familiar from linear algebra. If we find a vector where L times this transition matrix equals L, we're really finding an eigenvector that goes with eigenvalue one, right? There's a nice theorem called the Perron-Ferbenius theorem that you don't have to stress out about too much but it says if your matrix is full of probabilities like this, the largest eigenvalue is one and the largest eigenvalue is called the dominant eigenvalue. So when we do this we're really looking for what's called the dominant eigenvector. And if you've taken linear algebra you see the size of this matrix and go there's no way I'd wanna find all the eigenvalues and eigenvectors and my computer feels that way too but there are special algorithms to find the dominant eigenvector. So good news, the special algorithms work for exactly what I need. So 25 hours in the computer later I get out this giant vector of the long-term probabilities of all these 6,720 states. Why are these first five not surprising? Yeah, those are the amounts of money where there's only one way to make that amount of change and so I expect to see them one one hundredth of the time. When you get to five cents, apparently most of the time you'll see five cents as five pennies and then the rest of the time is a nickel which didn't even make the top hits list.  So the expected number of coins in your wallet is slightly more than 10. And here's the distribution of expected number of pennies, nickels, dimes, and quarters in this model. Fun fact, if you look up how many coins are in circulation by the US Mint, this is a lot closer to what the US Mint has out than my brother's model of just throwing it all in the jar for whatever it's worth. This one was not surprising. We saw it on the previous slide. One one hundredth of the time you expect your wallet to be empty, but almost 60% of the time you expect to have at least a nickel, almost 96% of the time you expect at least a penny, a little over 8% of the time you'll have only pennies and it's a little bit less than 1% a chance of being able to pay any price with exact change. So you can figure out all kinds of things if you believe the assumptions in my model. But let's see, that's not the whole story. We've been questioning assumptions throughout this, right? So was that price distribution the reasonable thing or do you really act like a coinkeeper or do people really spend money the way I describe? My friend and I realized not everybody spends money in the same way and so we tried out a few other options and I won't go into great detail about them because I see the time but here are some things we looked at that I think might be fun to think about who does this. So penniless purchaser, that's someone who only uses nickels, dimes, and quarters. Who's a penniless purchaser? Well, if you're Canadian you are because they stopped minting pennies five years ago. Okay, so that's a model with a lot less states. You only have the silver coins. In fact, it's 213 states I think and I can say more about that in questions if you're curious. Who doesn't use quarters? What's a reason not to use quarters? To pay tolls. To pay tolls or maybe live in an apartment and you gotta save them for your laundry? Some interesting things happen if you only use pennies, nickels, and dimes because what might've looked like four cents versus 54 cents before, you swipe the quarters and those collapse to be the same thing. So it's suddenly more likely than 1% of the time to see four cents if you're swiping your quarters on the side. When we were setting this up I told my collaborator I don't think I spend like the thing we just did. I think I try to match the ones digit in my prices with pennies first and then I treat the silver coins like we just described. So we ran that too. And then this last one's weird. Jeff Shallott is a Canadian mathematician who wrote a paper called What This Country Needs is an 18 cent piece and it wasn't just crazy talk. He was asking another optimization problem with coins. He wanted to know what collection of coins should we have if we want to minimize the amount of coins you would hand over per transaction. And he discovered that you'll have less coins handed over if you replace dime with an 18 cent piece and you see that's in your lifetime as well, right? So there are mathematicians who think about these kinds of things for fun. So I've purposely put in shortcuts here. My slides will be available to you after the talk if you're interested. But I'm going to skip to the end here. What do I hope you got out of 45 minutes of coins? Two things I hope. Number one, always think about your assumptions, right? They affect the kind of answer we get. So if you're trying to model something, assumptions matter and it's good to question them and make sure they're really modeling things as accurately as you hope. There's something else too. And to get at that, let me show you a quote from one of my favorite books. This is from Letters to a Young Mathematician by Ian Stewart. He says, I sometimes think the best way to change the public attitude to math would be to stick a red label on everything that uses math, math inside. There would be a label on every computer and I suppose if we were to take it literally, we ought to slap one on every math teacher. Good luck trying that. But we should also place a red sticker on every airline ticket, every telephone, every car, every airplane, every traffic light, every vegetable. I would add every wallet. I hope this has challenged you to look at the everyday objects that you see all the time and think a little bit more about the math behind them. So this was based on a paper I wrote with a friend a couple years ago. If you're interested to see more details, you can look at the paper. An early version of the paper was reviewed by a Scientific American blog and that's actually a fun read too. I'd recommend it. And if you're interested to see the parts I skipped over at the end, the slides are already on my website. Thanks for listening.


Test, test. All right. Good morning, everyone. My name is Josh Chai from Infiniti Soft. We're the software company dedicated in hybrid cloud management. And our goal is to make hybrid cloud adoption easy and simple. Who is Infiniti Soft? We're actually specialized in a software field, and we came from Java background. We were doing the projects for most enterprises, so we understand most business needs for adopting cloud. The cloud today, what we see is not the same. All clouds are not created equal. So the cloud, including the pricing tag, characteristics, how you're using cloud, even the location are different. Also, clouds are complex. Which cloud you should be choosing? You should be choosing based on performance, or you should be choosing based on characteristics. But all the devices growing today from wearables, cell phones, even smart cars, all the smart devices make cloud even more complicated. Because most important thing is, you need to make a cloud close to the user as close as possible to make your service be more efficient to increase your quality of service with consumers. What we do with Infiniti Soft, we make hybrid cloud management centralized. Meaning, it doesn't matter if you're using one or two version of OpenStack, zone one or zone two, or you're using VMware and other hypervisor solutions. We make it centralized in a single interface. Also, we have a completed cloud ecosystem. We make resource management. We make analytics, as well as a deployment easy. And we allow your service to be able to deploy to any location in the world. This is how our solution looks like. The solution has three products included. First product is CloudFusion. And the other product is a log loop. Literally, it analyzed a log from different sources. And the last is Apple Loan. So let me first introduce CloudFusion. CloudFusion, so far, are connected more than 10 different cloud resources, including different hypervisors. Doesn't matter you use which public clouds or private clouds, we're already connected more than 10 most well-known cloud resource already connected. CloudFusion, also, is a one-step platform allows you to jump straight to three most important characteristics in cloud, including self-service, including measurement, as well as a organization resource reporting, and all the flows. How does CloudFusion relate to OpenStack? We're actually adding more features and benefits to the OpenStack community. We make OpenStack be more easy to manage, give more functions, including charge back and self-service. So you'll be able to connect, for example, adopt two versions of OpenStack, because you know OpenStack have a revision every six months. With CloudFusion, you'll be easily to manage a different revision of OpenStack, as well as a different branch from OpenStack. In my slide, it's actually for SUSE, OpenStack version. Very quick interface screenshot showing you the CloudFusion. However, I will take the next half, 10 minutes to go through the product demo. So just give you a quick snapshot about CloudFusion. On the left-hand side, you can see different features of business needs. Also three different hypervisors right here. The secret behind the CloudFusion is our open source project. We actually have Skyport public on the big bucket, as well as a Github. Skyport is an interface connecting to multiple clouds. It doesn't matter if you use multiple private from OpenStack version, different OpenStack versions, as well as a public cloud. Our open source project, Skyport, allows you to connect to multiple sources, make it easy to manage. And you can also add your own drivers, why not? A quick interface showing you the Skyport. The left-hand side showing you many virtual resources you may have from different public clouds, as well as private clouds. Another project from us is actually contributing to OpenStack community is called Keystone4j. Keystone is actually one of the elements of OpenStack, a managed authentication, because we all know OpenStack built on top of Python language. What we do is we came from Java background. We actually make this little program allowed user to adopt OpenStack Keystone module easily from Java. We use RESTful APIs to allow Java users to enjoy the functionality of authentication from Keystone. Second product I'm going to talk about is LogLoop. So literally, LogLoop collects log from different sources, including OpenStack, as well as a hardware resource, OS resource, system resource, as well. All the log is all the text form, so it's not easy to see why you can get from log. Log usually looks very complicated. What we do is we're first of all collecting log from different sources, do the indexing, so you get easy to do the query from us using Google language. We can use log to make a graphical interface so easily to use this information to do your revision, as well as to judge your virtual resource. Last but not least, Appalone. Appalone is a product. Actually, we all know automation. Automation use a lot of script. So we actually transform and convert script to the GUI interface so you can enjoy the automation by GUI easily to deploy your service. As well as Appalone gives more manageability for you to deploy applications to everywhere in the cloud. So I'm going to finish my presentation as a quick introduction. Next, I'm going to demonstrate our product. So this is our goal by simply a hyper cloud adoption. So what I'm going to do is let me just quickly log in the product to the live demo. So this is Cloud Fusion. So from the first dashboard, you're going to see easy to see two different open stack version. We give you a zone one and zone two, as well as you see our resource in Beijing from Aliyun, a different hyper cloud management functionality. We also manage VMware, as well as RGV from Red Hat and AWS. So most of the wanted feature for enterprise when they adopt open stack when it's a cloud is you need to set up organization. This is most of the wanted feature from when you adopt cloud. So in my case, I set up InfinitySoft as a company layer. Again, you can easily set up multiple companies if you're MSP. So in my case, I have Japan branch, China branch, and three branches, as well as one resource for partner. So under my branch office, I have a different BU functionality. I have three R&D group. I can limit them by the functionality and the rows they are actually working on. So in this case, RD1 actually for the front end. Going to the row, as a front end engineer, you can restrict them the resource they can use on the cloud. For example, a restrict front end resource of engineer can only use AWS as a testing purpose or for developing purpose. So this page actually demonstrate you can actually you see the cloud resource. Now you actually be able to allocate a resource to your specific department. This is very important for enterprise to adopt cloud. So now you already set up the organization. What you're going to see is you need to set up a breakdown resource by companies. Again, we use AWS. You can limit it to different individual companies. Or we go down to another level as organization. Again, that's a sign, open stack zone 1 to another specific organization you may have. So for example, I have maximum 23 CPU. I can give Japan branch for five. I can give memory as a 43 gig. I give four for Japan branch. So now they will be able to use a specific resource that you allocate to them. Again, we go down to another level. You can even assign resource to a specific user group. So this is a maximum resource you have as a cloud maximum capacity. When you do all this arrangement and allocation from resource management as well as you set up your organization, most important thing is you can see the instance. This is a multiple instance you see from zone 1, zone 2, from open stack, as well as from different regions. In my case, let's try open stack zone 1. From this reds and greens, what we already been done is we connect VNC to your virtual resource to different open stack version. We can also go inside to click to see the detail of instance. In this case, we can see the life or see the duration of instance status. Here's has another module here called payment. It's very easy to understand as all the resource should be measured. So one of the important things as infinity solve is we actually give a customer a measurement so they can do the charge back to different departments. Not only for virtual resource, you'll be able to see the status. If you go inside the hardware, this is a host of your cloud hardware, which is what we call host right here. Different IP address represent your hardware so that say we try the first hardware. Again, you'll be able to see the life status of your hardware. It's your hardware environment. It's time to upgrade or it's your hardware capable supporting all your virtualization platforms. Template is also very important because Cloud Fusion actually pulls back life from different cloud platform you may have. So let's go to do a charge back function. It'd be easy to understand what's charge back. We have pre-set up charge back programs here. So let me create another new charge back. We give a name, a name of new charge back module. And we actually can assign different CPU. In this case, template is very important because we choose currency that shows a template from pullback from the OpenStack group. So we pull back from OpenStack, easily pull back a template. So you apply the template to your charge back module. So now you're easily to apply different charge back function. For example, running for Ubuntu, I give a price of $4,000 yen. Why not? Also, I give a price of applications. So I can say we run Office. So those are the costs of IT people. Admin people should be able to manage your organization more efficiently. So in this case, you're done. You set up one price plan as a charge back. You can also list, sorry, you can also list all your software functions and a currency right here. Workflow, workflow easily to understand is we can manage day and line, manage different servers. Sometimes you need some of the job to be done at night so you can shut down some of the server at date, start up some servers at night. Again, we all manage the virtual resources. Reporting is the same. You can report by different duration of time to get back your management to see the real cloud utilization. Scheduler, again, managed all the VM. Scheduler work together with workflow because workflow allows you, once you set up a hierarchical infrastructure organization, we allow you to authorize and resource allocation. Management easily to deploy the management functionality. So we're glad to be here of OpenStack Tokyo. If you have any questions, please visit us at booth T57. It was our website and we're infinity soft. We make a hybrid cloud adoption easy and we release the true power of a hybrid cloud utilization. Thank you very much.


Good morning, everyone. We are going to talk about Rust based but I have backends for Hypervisor Exhaustic Solutions today. There is a growing trend in the current market to implement virtualization for market health other than the traditional server environment. The server environment is very uniform in nature, but as we move towards richer ecosystems of automotive, mobile, medical, and IoT, a very richer ecosystems, organizations, and more device abstractions are required. At Linaro, we started Project Stratos with the aim to make VertiO as a standard interface between hypervisors, playing mobile, automotive, and all these different platforms to migrate from one hypervisor to another one without the need of implementing the backends again. Myself, Viresh Kumar, I work as a senior kernel engineer at Linaro. I co-maintain KubeNamex in the Linux kernel. You have already met Alex, Alex Manny. He's a senior virtualization engineer at Linaro, and he leads the Project Stratos. We'll quickly go through the introduction to VertiO, Vhost, and Vhost user, how they have evolved over the years. And then we'll go to what we have been doing at Linaro in Project Stratos and what we are looking to do going forward. So VertiO was designed as a standard open interface for the virtual machines to upload their data path processing to the host kernel or to the host kernel or the host user space instead of the guest VM. VertiO defines two entities, one at the host and other at the guest. The entity at the host is responsible to share its word queues, and the entity is called as VertiO device. It basically emulates the device, the virtual device. The entity running at the guest, it is known as VertiO driver. It shares its word queues, which are then accessed by the host device. There are various transports which are already implemented for VertiO, like PCI, MMIO, Channel IO. Though a point to note here is that the higher-level device abstractions, like a block device, they are very much independent of the underlying transport mechanism. This slide shows the basic sequence of events that take place for a VertiO transfer from the guest to the host. On the right side, you can see the guest VM. On the left, you can see the host VM. The host VM is the one which has hosted the guest VM. So they are on side-by-side. A normal write operation, a write syscall to FD, eventually reaches to the VertiO block driver on the guest side here, in the red block. This driver is responsible to prepare the data packets, put them into the word queue, and send a kick to the host kernel. When the kick is sent, the VM exits at this point of time, and the control reaches to the host kernel. In this particular case, the backend, the vhost user-demon is implemented in user space, and it passes the, so the host kernel passes the control to the VMM running in user space, and the backend, it reads the event FD to get the notification. It processes the word queue, reads the data packets, and if required, programs the hardware, the block via the write command, and it already has a map the device. Once it is done, it may update the status of the word queue and then send a call back to the guest VM. One important thing to note here is that VertiO is an asynchronous protocol, so the guest doesn't need to wait indefinitely for the host to complete this operation. It can go on, and a response will be sent at a later point of time. While at it, let's also see how it happens in case of Xen. In case of Xen, the VMM is not responsible for doing all this. The VMM is only there to create and destroy the guest. Rather in this case, the backend implements a Xen specific thing, which is Xen Iorek server, which enables the backend to get events and information from the guest kernel. And this is the layer which is responsible for processing the word queues. Vhost is a protocol to upload data path processing to the kernel from the guest VM. The processing, of course, in this case, happens in the guest kernel, for the VMM to share the word queues to the host kernel, the interface is provided via, the control path is provided via the IOCTLs. This slide is pretty much same on the guest side. On the host side, the main difference is that the processing happens within the kernel. So when the guest exits, does a VM exit, at that point of time, the host kernel comes up and it, the adapter there, it goes and process the word queue, all the data in from it and then eventually sends the returns back to the guest. Here, the VM, if you see here, the VMM, it implements the Vhost IOCTL for the VMM to configure the various word queue information to the kernel driver. Vhost user protocol, it complements the Vhost protocol in a sense that the control plane is implemented via Linux domain sockets. The main purpose of Vhost user is to implement the back end, the Vhost user daemon in the user space instead of kernel. The Vhost user protocol defines two major entities, one is front end and one is back end. Front end is the entity which shares the word queues. It looks like the word IOCTL driver in a sense, but it is really the VMM, like QM in our case, which shares its word queue and back end is the entity which consumes the word queues. This shows the word Vhost user path. So it is very much similar to how it looks in case of Vhost. The major difference is that the standalone user space device emulation daemon is sitting in the user space which talks to the VMM over the Vhost user protocol using a unique socket domain and it processes the word queues from the guest. As I said earlier, Linaro's project stratos was started with the aim to make vertio the standard interface, allowing all these platforms like IoT and mobile to make the back end spotable between hypervisors. Right now, QEMU has some of the Vhost user back end implemented within it, which can run independently of QEMU but they share a lot of code with QEMU right now and they are not really independent in that manner. So and we have been looking to make these back ends hypervisor agnostic. So the same back end which runs on QEMU with KMVM can also run on Xen and on some other hypervisor like cloud hypervisor as well. We have done a lot of work in around one and a half years until now with just a bunch of engineers. We have worked in all different categories like, so we started with what are specifications. We wrote a few of our own, reviewed a few, sent improvement patches for a few of them to the what are specification. We also implemented kernel drivers, reviewed some of them. The main thing that we have done is implemented the Vhost demons in user space which are supposed to be hypervisor agnostic. While doing so, we implemented the back end for GPIO and chose LibGPID to be the intermediate layer and we were required to add support for LibGPID as well which was very time consuming. In the process because we wanted to emulate the device on QEMU and Xen, we did develop some patches there as well. We tried to upstream first. We are upstreaming everything that we have. There is nothing which is closed source as of now. So Rust, Rust is a new language which is making its way into the embedded domain nowadays. We will likely see it into the Linux kernel very, very soon. Initially, we developed everything based off C and we thought maybe it's good time to try Rust. Rust is a language which guarantees performance, safety and concurrency. It is of very high importance in our case because we have to handle entrusted guest data at the host side and the guarantees that Rust provides are really, really significant in our case. And then Rust is cool. Everybody talks about it nowadays so we thought maybe we'll give it a shot. Rust VMM is a framework. It's hosted in GitHub normally. It's a framework for building VMMs. For example, there will be a create. Create is like a Git repository you can say but it is still different. So there's a create, a module for Vhost. There will be a module for Vhost back end, Vhost front end. These are all different modules which when combined together they make the real thing. So there are many hypervisors which are already using and sharing these modules like Cross-VM, Firecracker, Cloud Hypervisor which are heavily using these Rust VMM components. So whatever we have been developing we are trying to upstream into the Rust VMM project because that is the most sensible project where we can upstream all this stuff too. When we started, the Rust VMM project did not have any specific create where we can upstream the device implementations, the device simulations. So we created a Vhost device create for our own. It is currently maintained by Leonardo employees, Alex, me, Matthew Poirier. He's not here today. And we have already upstreamed quite of them like GPIO, IOTC, Random Number Generator. While there are some others which are still in progress. RPMB and SCSI and VSOC. There are pull requests which are there for implementing the Rust support. While SCMI and video, they are C-based right now and we are looking to migrate them to Rust as well. One of the common thing here is that the current implementation is very much Linux environment specific, like we access the device from the dev interface since it's FS in the kernel. But there are some which are bare metal like SCMI. It is a bare metal implementation, but right now in C. So initially we developed everything with QMU because it was easy, fast, we can just do it on our machines. Once we had a couple of backends in place, we thought, what can we do now? Because we are claiming that they are going to be hypervisor agnostic, but we have only tested them with one of the hypervisor, KVM along with QVMU. We thought which is the hypervisor which makes more sense to go to. And Zen was one of the choices we had because it's a type one hypervisor. It fits very well with the arms model of hypervisors. And then it has good upstream support. There is a good community around it. So we moved to Zen. When we moved to Zen, the problem was that a lot of stuff was not there, like we host user protocol. These were not implemented for Zen. All that we could find was there's a disk device emulation which was written in C for Zen where they have implemented the way they can pass the word IO packets, the word queues and all. But the V host user was the main missing thing which was there already in QVMU when we started. So now we have a working setup where we can test the existing backends, unmodified with Zen. And we have already proven that the backends are really hypervisor agnostic and there's a lot of hypertracks right now to stream a lot of Zen bits into Rust VMM and into Zen as well. If you see this slide. So this is the main component that we have added. There are three things here. We'll come across that. These are the three entities which are basically bugged on by us in the Zen site to support V host user and test the existing backend. The existing V host user, demon is this one. It hasn't changed since QVMU. This is the new part which we have to do for Zen. There are three main components here. The first one is Zensys. It is developed by Matthew Poirier. This basically provides support for Zen hypercalls via iOS CTLs and bare battle. Then we have V host user master. The V host user master create was, the basic purpose of the create is to provide the V host user front and side of the development. The Rust VMM community already had the backend side of implementation and we could use it earlier for the backends but the front end side, they did not have. Luckily in our case, the cloud hypervisor did implement the V host user master side and we were able to fetch a lot of stuff from there, add some things out on the top of it and make the V host user master create. Now this create is not Zen specific. It is very much hypervisor agnostic. Anybody who wants to implement V host user front end can use it. QVMU can use it for that's it. If they want to use a Rust based implementation. Zen V host master is a V host user master implementation specifically for Zen which has all the sequence of event you need to do for mapping the memory, the Zen iorek server thing and it uses V host master side as well. V host user master create as well. It is based on ePems, what I would disk implementation as I said earlier which was done in C but it did not have any V host user protocol implementation at all. When we moved to Zen, we wanted the backend to be really hypervisor agnostic. They still are, but there are challenges which we have faced. In case of KVM, the guest memory is mapped via Dev SHM. These are user space pages and but in case of Zen when we moved it. So with Dev SHM, the main benefit is that we can follow the standard Linux kernel way of mapping the pages. We can just do a map and everything will be fine. We will have the guest memory available to the host kernel, to the backend and it works fine. And that is how the Rust VM projects are aligned. They just do a map and they expect it to work. But in case of Zen, the Zen community couldn't use the user space pages. They had to move to kernel space pages because the kernel sometimes sets the page table entries to invalid state and if Zen comes and tries to access the page at that particular time, they get a fault. And because of that, they couldn't use user space pages but they have to move to kernel pages. For implementing that, Zen supports a lot of hypercalls, not just M-Map and to have a uniform way of doing all the hypercalls, the way they implemented is that for M-Map, you have to do M-Map first, which will set some flags and all, but eventually you have to issue an IOCTL. And this is where our system broke because we thought that M-Map should be just enough. And we do not want to implement something which doesn't work well with the Linux call way. So we expected M-Map to be robust enough and it should just work, but it does not. For now, we have hacked the kernel for Zen in driver-zen-pref-cmd file. We have hacked it in a way that everything which is done by IOCTL for M-Map is done in M-Map itself. It works right now for us, but it is not a solution we can upstream and we still needed to find a solution for this. What's next? So we have been looking to upstream Vhost user masterquate, which we picked from Cloud Hypervisor and then Vhost master, which we have implemented ourselves. We already have few pull requests to the Rust VMM community in GitHub to get things started, start merging these things bit by bit. We need a standard M-Map interface, as we discussed earlier. We think that there's opportunity to improve the performance by reducing the number of contexts which are required for IRQFD and EventFD from the guest to the backend. And then there is space for guest memory space privatization. We'll cover them one by one. So this is a previous slide. This shows indirect IRQFD, EventFD. So when the control passes from guest VM, VM to the host kernel, eventually it reaches to then Vhost master here, which is implemented via Iorek, ZenIorek. When the event reaches here, that some data is present in the word queue. We send the EventFD from here. It again goes into the kernel, come back to the backend. So we wake up the user space just to wake up another thread. And there's an unnecessary context which to kernel and then to user space which you want to avoid. What we think is if the kernel can somehow handle this interrupt from the VM and straight away pass it on to backend, it will be great. We do not have a solution for it right now, but I think Paulo mentioned something this morning regarding in kernel event delivery that can be very interesting for us. Then comes guest memory space privatization. So in the current setup, the backend can see the entire guest space, which is of course not ideal because we may want the guest VM to be secure and it doesn't want to show its entire user space, its entire space. The word queues in the guest VM are always mapped in the host side. So the host can always see the word queue area, but the data buffers which are filled by the guest, they are, that is the tricky part. So there are three solutions how we can map that. The first one is per request map. This is something which Zen community has already agreed to to some level and merge some of it in the Linux kernel. It is known as ZenGrant or IOMMU based solution. The problem here is that potentially there can be multiple buffers for each whatever request and then we'll be required to do a map for all these buffers on the go for every single request and we worry that it will be too slow and it is really not efficient. But this is already merged and we'll see. The other solution that we can think of is carved out region where a fixed region is set up between guest and host where all these buffer will be copied but then it will not be zero copied, it will be fast but it will have its own problems. And the last one which was again suggested from Leonardo by Arndt Bugman is fed word queues. The idea here is that since the word queue memory is always mapped, why not put the data right into the word queue? But the problem here is that if the data is small, yes it can make sense but the word queue memory is not infinite, it is still finite and we cannot put really big chunks of data into that. So there are a couple of solutions here but we do not really know what's the right solution to go forward with it. That's pretty much it. You can join us at Project Stratos webpage. We have a dedicated mailing list where we discuss all the things that are going on. We have fortnight list Stratos meeting and Rust VM meetings as well where you can join and discuss if you would like. So that's pretty much it. If you want to ask any questions, me and Alex are here. Do we have time to do questions now or are you? Yeah. Any questions? Obviously not, okay. So if you have any questions come to you just grab us during the rest of the forum and we'll happily answer them. Thank you. Sure. Sorry, what was that? So the question was what our general experience of switching over from Rust to C. From C to Rust. C to Rust, sorry. Yeah, neither of us had done any Rust before so it was a fairly steep learning curve. I tried to dabble with Rust before a couple of times and generally just got lost after I'd gone through the first Hello World examples. What really helped for me was actually going on a week long intensive course where I could do Rust every day and get the model in my head. How did you find it? So I think Alex started the Rust training first while in my case I did write a couple of backends and upstreamed them before I got a chance to do the training but it's a fantastic language. I cannot really promise what they promise. They do guarantee that there are a lot of things which like the performance will be as good as what you can see and see. I cannot confirm it because I've not tested it at a great length right now but the language is fantastic. The kind of problems it solves for us like the races it avoids and all this is really, really good and it's an easy language to learn. It's not really difficult. Just a few things and that's it. I think the main thing is getting your head around the Rust model. It's like pointers so you have to understand pointers and then everything is fine.


This video was brought to you by my patrons. Thank you so much for your support Hello there. So yeah, now I can record on full HD, but that's not of the concern of this video But I think that I've been using and maybe you've been using the process and all the good old building callbacks in the wrong way, or maybe we didn't realize some Problems with the current way that we approach the callbacks. So with callbacks I mean the already callback the process callback the files callback. Anyway, all the virtual methods that go provide to us So let's go into an example that I have and let's see What's the problem and how we can work around it? So let's get started So I am with the combat prototype from kitchen tails. If you are not following kitchen tails Recommended to do because I'm posting a lot of stuff that you can follow on each IO and you can also follow the development on github I've put the link in the description but here we can see I will open the jump class and We can see that here. We have the physics process and inside of physics process I have a logic that will try to replenish the jump amount that the player has So it has a available amount that it decreases here in the apply method So it will try to decrease the amount of available jumps and on the physics process It would check if it can replenish this amount setting it to be the maximum allowed jump Let me show you what's the problem with that. I will put a very simple print here So we can see something in the output and I will print contact replenish This is the the logic that I'm trying to to make here when the player is in contact with the floor It will replenish the jump amount and now I will extend this class So I would save it and I will extend this class Extend script and I will call this one time it replenished jump let's say we want to make a Twist in the logic. Maybe we want the jump to replenish from time to time, right? So we jump and then two seconds after the first jump the jump is replenished Maybe this can be good for let's say flat bird logic or something like that So I will attach this this time it replenish jump to the jump node here So we can see that this is the script that it is using and I will Inside the physics Process at another print so we'll see what is the the logic that is currently bling being processed by the physics process So I will print time it replenish and If we test the scene now, we can see down here in the output that both Prints are being called so the contact replenish and the time it replenish and this is because Godot will call the virtual callback from the base class And the virtual callback from the inherited class, so it's calling both callbacks And maybe this is not what we want This can cause a lot of bugs imagine that you have three classes stack it So you have a hierarchy of three classes and you have logic inside this method What you can do and this is how I am working around that is that I will open the jump class again and Instead I will encapsulate this logic inside method So we can override this method because as you can see we are not overriding the virtual method from Godot itself So the virtual callback we're not overriding. We are stacking logic on on it So instead we can encapsulate this logic. Let's say I replenish Method and I will create this replenish method here replenish and I will throw this logic inside This method and in the inherited class. So in the time it replenish jump, I don't even have to Use this process. I will just override the parent class replenish method and here. I will just print Time it replenish time it replenish If we see now, I will test this again You can see that now it is calling only the time it replenish method So it's printing only time it replenish. This is because now that we created a method that we can reliably Override we can have our logic self-contained and we can override or maybe we can call the parent class Logic as well. So if you want to do that, we just have to make a super call by adding the dot before the call of the method And with that we will also call the parent class Logic as well. So if we play you can see that we have contact and time it being printed out in our output So this is my tip because I think that this Gives us a lot more control over the logic that we are using in the callbacks I also have here the platform action bus. I Used to have this filter event logic inside the unhandled input But now I just use it this filter event action because I inherited this class to make another class So for the combat action bus, but that's it with that We give more control to us over what will be called and what will be processed in The actual physics process because now we can safely override our methods or logics So that's it I hope this helps you build more reliable code And if you think that this doesn't make any sense or if you think that maybe something is wrong Or maybe there is another manner to approach this problem leave a comment below Let us know how you work around this problem And if you like it, please let me know by leaving a thumbs up This will help me a lot knowing that I'm producing something valuable to you And also if you want more of this content, please subscribe and turn on the bell I don't know if this works or not, but I know that less than 10% of my Subscribers actually receive or actually watch the content the new content that I'm producing So maybe this helps you get more content So I don't know if you to be what will actually deliver a notification for you, but this helps So that's it. Thank you so much for watching keep developing and to the next time