So the next talk, my question is about the next talk by illadruse us about making the
C-O-Mex con and so on.
So, thanks a lot.
Hello.
Thank you for the introduction.
Today I will be talking about what happens if you decide that working with your data structures
in a convenient way is simply to boring.
The agenda of this talk is, first one, I will talk about what was actually the trigger
to study all these.
And then we will briefly talk about the land of the lock free because all of this is
actually inspired in the land of the lock free.
And then I will outline the solution.
If the time permits, I will also out mention news in the C-O-Mex C-O-Mex kernel since
the last was them.
Okay.
So let's start.
What was the problem which made me to think about this?
The C-O-Mex kernel does its best to make life inside the interrupt service handler as hard
as possible.
The reason for this is that we run on very limited hardware where there is a rule that interrupt
service handler has to run in kernel mode or in supervisor mode.
So it essentially has kernel privileges and it can do a lot of bad stuff.
So we only allow two calls to kernel so you are very motivated to defer your work to
into user space, but this by this, you still can buy these two calls modify pretty much
every data structure that is there.
And while it is done from interrupt context, you have to somehow guard how to eliminate
concurrent modification so still things remain consistent.
You can't use mutex's because if you log mutex and you get interrupt, it's incentive that
lock.
What kernels do is they disable interrupts?
As I said, it's safe, it's good, but it's boring and it introduces a lot of latency and
also jitter if the thing you do with interrupt disabled varies in time.
So I've been thinking how to avoid this and I did some investigation.
I investigated how other kernels do it and I realized that many RTOs simply lock disabled
interrupts and call it a day.
Then I have a couple of friends and we have board game evenings with them and at one of
these board game evenings, I mentioned this problem, the constraints and what I want to achieve
and one of them told me, you know, this sounds a lot like you need a lock free approach.
Okay, so I started studying lock free algorithms.
I already knew some very basics of lock free and I guess you also know, but for example,
the case of single producer, single consumer queue, that thing can run without mutex's.
And it's inherently third safe because it's a lock free data structure in this one specific case.
Unfortunately, it cannot be used here.
So I've been searching for some other solution and while it was right around the time when LLMs
became very popular, I asked GPP. Okay, show me some experience which satisfies these conditions.
And it came bit roughly the similar, very similar code to these.
And what this code essentially does is that it creates a local copy of shared data under mutex.
But this is a one section, basically. Then doesn't modification on the local copy and then
commits it into the shared data, which satisfies all my criteria, except with one.
It has a lot of overhead. And it also looks quite a lot like database transaction.
Because you have read, modify, and commit stage. Therefore, I decided I will use this concept
general, but I will make it lightweight. Now, a bit about the lock free programming, what it is actually.
A lot of people think that if you have lock free programming, it means that you are completely
free of any locking. And nothing in the system ever gets blocked. Well, there's no true.
The definition of lock free is that at least one execution context does not block.
And here in the specific case, when we are talking kernel versus interrupt,
this context which you don't want to interrupt SD interrupt service handler.
So what we want to achieve here is essentially a fast line for interrupts,
which kind of allows us to cheat. If you find this guarantee that you only have one context,
which has fast line, to boring, then for you, there's a way to free programming. We actually
does the part that nobody uses locks, and nobody also gets blocked. But that's a lot more complicated
and you get a lot more overhead. Which is actually the reason why not everything is lock free,
because lock free comes with a lot of baseline overhead, which kind of gets paid for
if you do massive concurrency, where the overhead of locking is much higher than baseline overhead
of lock free algorithms. Now, when we know roughly what the lock free is,
and we know that the baseline idea was something like transaction, let's look to
how the transacted part of kernel looks like compared to standard critical section.
The thing on the left is a critical section, modeled by mutexes. So at the beginning of
the access of shared data, you log a mutex, or internal, it could be
you disable interrupts. Then you find what you want to modify, and then you modify it.
And once you are done, you reenable interrupts. What transaction this does is that at the
beginning, you open the transaction. This is a read on the action. Then you find the entry
which you want to modify. This is not an exclusive action. You can be raised by someone else,
both opening transaction and accessing the data. Then you try to commit this transaction,
and you specify that you are modifying the data, that you are going to modify the data.
And this transaction may either pass or fail. If it passes, then you get exclusive access
to this data, and you can modify it. If it fails, you shall not modify it because you will
break the contract. And then once you are done modifying it, you call the x and then
you signalize, you are done modifying the data. So the difference is that the critical
section is runs executably the whole time. Transaction only runs exclusively for the time you
are modifying the entry. It gets even more interesting if we consider the read only case,
because this is a read wide case. So, if you read some non atomic data from shared data
storage in concurrent system, you also use critical section to get the data in consistent state.
With transactions, you perform the wall data access in a shared state, so you can be raised.
And you can be raised even by someone who will modify the data. And the question is, okay,
why would you do that if you have synchronization primitive, which doesn't actually guarantee
consistency of the data? Well, it doesn't guarantee you that nobody will modify the data
structure, but at least if you survive it, it will tell you that it was modified. And the
beginning I mentioned that transaction start is a read only operation. And this read only
transaction has a nice feature that as a wall, it is a read only operation, including the
overhead of transactions up system. And that means that readers don't block each other, readers don't
block writers. And if you write something which someone else is trying to read in between,
readers will know that the data has been modified. And also there's if, which means that you can choose
how you react to the event that you've been raised by someone else. Okay, to detail a bit about
the transactions. What do you usually know as a transaction? Is an acid compliance transaction
from the database systems? These transactions provide a serialization isolation level.
So you can essentially take a list of transactions, replay them in the same order, and you get the same
state each time. Which is actually used by the database systems to do Keter Schroek Recovery.
And this level of isolation is nice for a database, but a bit of an overkill here,
because we would have to do the coppy from shared to local modify and then commit. And it will
also have to provide some temporary storage. And for microcorner running on micro control,
that's not really viable. And I believe it's not really viable for any microcorner anywhere,
because that's really high level of overhead. But there are other over separation levels.
And one of them is so called read committed. In this separation level,
all readers only see the data, which was committed by someone else.
And it turns out that this is just enough separation level, you need to live in kernel
in this weird partially synchronized or partially consistent state.
And therefore, if you run unicore, this framework offers this separation level,
which means that the data structures, as a wall, if you take some hash table or let's say
scheduling table, they may develop some unusual properties, like you have two threats running
on the same core at the same time. But the entry for individual threat is consistent.
Then, as I mentioned, the fact that read-only transactions are purely read-only actions as a
wall, they don't block each other. And you only pay for the overhead of transactions once you get
content shown. And for the just for sake of terminology, if a transaction
if you commit a read-bright transaction, it will invalidate any other transaction which is
implied. So it was opened, but it wasn't committed yet. And when transaction is invalidated,
it will fail to commit. Read-only transactions don't invalidate anything, which is the point of
non-booking each other. So, now, it isn't all roses, of course.
While this is all based on walk-free, we are essentially trading walking for iteration. So when
you get content, the thing you probably want to do is retry. But there are cases, as I mentioned,
you are free to decide what to do. And there is one case. It is actually the first case where
we implemented this, and it's scheduler. Because it may happen that you have normal
scheduler run. So we are deciding the next threat. And then interrupts comes, we change this
state of threat. And it fires another scheduler run, and they run concurrent, one on top of
that another. And in this case, what happens is that the scheduler from interrupt changes state of
threat table, decides new threat, set seat, and returns. Then kernel finishes, and his transaction
for scheduler fails. So what does it do? It gives up. Because someone else already did scheduling for it.
That's a nice feature. For the interesting properties, it means that your algorithms
have to be resilient. You cannot assume that there will be only one max value in something which
has unique values. Which is still good if you are running a unit processor, because there's
this read committed separation. So like internals of the data entry itself will be consistent.
Because whatever race to you did the change automatically because interrupts were disabled.
But it gets very funny when you switch to a multi core because there this assumption doesn't
hold any more. While interrupts are disabled on one core, someone else may read on another core.
But you also need to another problem. It's actually next slide.
That, as it is implemented right now, it only works in Unicorn setups. Because currently,
we commit the transaction at the beginning when you call an transaction commit.
And if you were running multi core, there would be an ambiguity that if anyone opens
transaction while you are inside commit, which is technically possible.
You couldn't say if you have to abort this transaction or not, as an effect of the transaction
which is currently being committed. And there are two possible solutions to this.
Synchronize opening transactions, starting transactions with commit.
Well, it will remove the feature that your read only transactions are read only operations.
But it's the safer way because you get this synchronization and it's clear.
And another option is that we will mark the transaction as committed or the internals synchronization
point will be marked at the end of commit, at the point when you call transaction done,
which also provides the synchronization, but you don't need to use mute access.
So this is the next update which will be done.
Maybe why do you consider transactions? Maybe you think that this must be like
crazy complicated framework. Actually, it's like 95 lines including commands.
And the memory overhead is like you need one field for to remember which was the last committed
transaction ID. It's really trivial. And as long as your data structures and your algorithms
can survive this violent, inconsistent, internalized, internal state, you may benefit from it.
I don't know what will be the general performance of this for two reasons.
Some external case is kind of specific. Our kernel is designed that many actions which we
transacted have quite a long phase where they are finding the entry to modify. Like we are
searching, okay, you want to change the thread state. So search for a thread, take some time.
It's not a one operation and then you change one flag which is one operation. It's a one.
Your mileage may vary if you use different code organization. And then, which we don't know yet,
also, is how funny it will become when we go multi-core. Because there's a lot of unknowns,
which I cannot predict what will happen, what synchronization problems will pop up.
Okay, and we have some time. So let me to list out some news in the kernel,
kernel itself, got support for FPU, which is nice because we can use more performance.
New Texas were moved out completely into user space. For the happy path,
the thing you are watching right now is actually running inside CMRX. So it's not the presentation.
It's an actual application, running on an actual operating system, running on top of Linux.
It's an automation. We are using Linux as a hardware platform. Another platform which was
added is Rmv8 and community slowly growing, with more ports coming, namely risk 5 port,
which is contributed by another guy. So thank you. Are there any questions?
Questions?
Correctively, you introduce an intentional race possibility in the transaction period, and I'm just wondering,
so isn't that technically undefined behavior, and does that product problems in practice, or was?
Uh, depends on what you ask. If you ask something from academic sphere, they will tell you yes.
Uh, if you ask someone from the field, they will tell you yes, but if you survive it,
you will be, you will be told that it was an, and you, you went through the field of undefined
circumstances, so you should probably throw the result away. And it's up to you to decide what you
actually do, because you may say, okay, whatever I computed is a garbage, but the conditions,
which led to this garbage, which you actually control in that application, because you decides
the transaction domain, with using it, what, what is the semantics of the data you cover by
transaction, like in the scheduler case, it may mean, okay, someone did it for me, so I just did up.
Have you looked into read copy update, because that's a scheme that sort of should provide you with
some more properties like readers, not being synchronized among each other, writers not being
brought by the readers, readers not being brought by the writers, and I would say the main difference
is that compared to transactions where you have to tolerate failed transactions, in the read copy
update, you have to tolerate that the readers might see still data sometimes. So would that serve you
well or not, and if not, why? Okay, the question was if I check the read copy update,
I think it's from Linux, or, okay, yeah, about the Linux is it, the answer is I haven't,
because somehow when doing my research, it led me to some obscure mechanism for very specific
situations, and then I switch to book free, so I skip this, but it's not read as well,
it's a different approach to the same problem, and you have different trade movements.
Yeah, so now I haven't studied, but you are actually the second person who mentioned it, so I will
definitely study it. In the forward row, yep, when you say like,
lock free decision, like you introduce what I would call intersectional memory, or in this case,
of intersectional memory in the front row, and when you talk about lock free, you talk about
that's not very interesting, I'm sorry, I don't know, it's not fair if you're talking about
the good meaning of lock free, or something else. Yeah, so like it's not completely lock free,
it's inspired by lock free, and you actually have the good, you have good points, and the question
was, if it is lock free, if it actually locks, right, kind of, and the truth is that it actually,
you know, when you go multicore, this locking will actually be quite useless, because another
core can bypass you, unless you do interprocess, signaling, and lock everything down, and when
you are resilient enough to survive the hell before the comet, then you actually don't need to lock.
I think I'll just suggest that you take a look at the sort of transactional memory.
I think that we are out of time, so we will take questions outside. Thank you.