Could this be changed to "with pytest.raises"?

Sleep? What's this for?

Could we name the test "test_ri_and_mep_cache_corruption" then? :)

This set of defines could become and enum type instead? Not a hard request though, feel free to ignore.

Maybe a more descriptive name then? Like ep_create_time?

For my sanity, this is checking that if an entry is returned from the cache, it must not be in any of the three listed states?

Also a possible enum candidate? enums are nice because they give a "type" to where the ENTRY_CACHE/DN_CACHE can be used and means we can do better type checking of those values.

So I'm assuming here that this means "if the entry was added in the same second or newer", purge it? There is a risk here of flushing an entry from a previous operation, but I'd rather be "too broad' than miss an entry.

We could also set the "start time" to 1 sec less for paranoia, but I think this is fine since rel_time is always advancing.

Is it possible that another thread could change the content of ep_state but behind a different lock (entry lock rather than cache lock?)

Actually, there is a cache coherency bug here perhaps. If we do:

thread 1           thread 2
cache lock
   entry lock
cache unlock
                   cache lock
                        entry->ep_state invalid
                   cache unlock
read entry->ep_state

in this case, because thread 1 has no issued a new lock, no memory barrier was applied so the value of entry->ep_state may still reflect the value from when the entry was locked, and will NOT show the invalidation of the entry. So I think we need to be careful here ... We may need to lock the entry to change ep_state, but it HIGHLY depends on the usage of entry reads in other threads and how they assert safety.

Sorry for all the comments. Anyway, this is great work, especially isolating a test case that can prove entry cache corruption conditions. Awesome stuff!

Commenting on my own PR, is setting the state while another thread owns this entry safe? Perhaps a special uint64_t flag in the backend entry would be safer?

EDIT: Errr sorry missed @firstyears comments here because of Pagure webhooks not reloading the page. Okay, so we all agreed this needs more attention :-)

I have addressed @firstyear concerns. I now use a unit64_t to mark entry invalid, and use atomic store/load to set/check the value. This should address the memory barrier issues (but please correct me if I am wrong as I am not an expert on such things)

Please review...

Little nitpick (but not your fault at all) this should be uint8_t instead of char?

Ahhhh @mreynolds ... you know how you allegedly liked me or respected me ... well, I think you'll hate me for this.

I was thinking a lot about this fix this morning, like, for a good three hours or so. And I think that even with the atomic changes, it may not work, there may still be a potential corruption condition.

I might make this comment a bit longer so that my understanding of this is correct and described. So there are two levels of locking - the cache lock that describes "what is and is not in the cache", IE it protects the hashtable. And each entry in the cache has an "entry lock" to protect it's content from threaded alterations. Each entry uses a reference count to determine if it is still in use. I'm not sure of how reads use this (whether they maintain the lock during an operation, or if they copy the entry for the operation).

It's pretty clear from this design, that a goal of the entry cache was to be concurrent, both to reads and writes. Now for this thought exercise, we'll assume there is only a single BE_TXN write thread (which I hope is true, but ... it may not be), and there are multiple concurrent read threads.

So let's assume we have two threads now, one writer, one reader.

thread read            thread write
---                    ---
cache lock
  get entry a
    lock a, refcnt++
    unlock a
cache unlock           
                       cache lock
                         get entry a
                           lock a, refcnt ++
                           unlock a
                       cache unlock
                       lock a
                         modify a (corrupted)
                       unlock a
lock a
  read a
unlock a
                       cache lock
                         atomic set invalid
                         lock a, refcnt --
                         unlock a
                       cache unlock
cache lock
  lock a, refcnt -- 
  unlock a
cache unlock

So the thing is how do we actually protect our cache from this behaviour, where the read that happens exactly the same time as the corrupted write lands, is isolated? I think our cache is not designed with isolation in mind at all, so as a result, I think this situation can still happen, even with the atomic invalid now being present (because there is time between the corruption and the invalidation occuring).

So in general, I think mark's patch is good to move the bar further, but it doesn't completely fix the corruption. We are butting our heads against the fact our cache is designed for "fast, simple, correct" not "correct, simple, fast", which probably means no amount of patching will ever be able to solve this bug until we rearchitect the cache - at the minimum to guarantee a single be_txn writer thread, and that entries that are "written" are in a staging cache in parallel then only commited when we can guarantee they are valid.

More specific to this patch, although the atomics do protect from the race condition I mentioned, the issue is that atomics are costly, so this will have a performance impact on the cache I think, which will be pretty significant (worse on numa systems).

If I were a compromising william, I think that I would do the non-atomic version of the fix (we still have corurption races, but they exist anyway, because of our cache design), because we don't pay the atomic cost. We'd commit that, then immediately start to work on the "staging cache" for writes, and making be_txn writes linearised.

Does any of this seem sane? Have I missed something or misunderstood something? Hope it helps,

@firstyear, correct there is no way to prevent the cache from corrupted entries (in regards to this fix). They will exist and be available to other threads until we we realize the cache is potentially corrupted and we remove them. While this window is very small the threat is still real, but this fix is not about preventing the corruption but about safely removing the corrupted entries asap.

I'm still kind of leaning towards using atomics here because although they are costly we know there are other bottlenecks in the cache and in the server in general. So at the end of the day are we actually impacting overall server performance with the use of atomics in the entry cache? I don't know, maybe not. But I think integrity is more important than speed.

You would know this better, but from what I understand using uint64_t somewhat works like an atomic, but I don't know if that applies in regards to memory barriers (probably not). If it does we just use the new flag but without calling atomic load/store (which is what you are suggesting anyway).

So like you said, today this fix solves a number of problems (it has value), but it does not address the underlying fault in the cache design.

Yes, we will be affecting the performance, it has a much higher cost when they are contended (and they will be contended in this case given how many threads will be hitting this). I agree that integrity is more important than speed, but I worry this will be a really big hit ...

uint64_t doesn't really work like an atomic I don't think. Best way to think of it is that memory is like a "timeline" when whenever you read that memory you are looking at "any value from the present to the past" but you don't know where on the slider that is. But with an atomic you are guaranteeing that the memory you see really really is the exact present value. So this is why the non-atomic version is not too "bad", because the refcnt is still safe, it's just that we have a subtle race where an invalidated entry may be seen as "valid" briefly by another thread. As you have said yourself this is already the case given the cache design, so having atomic vs non-atomic, doesn't really change that situation much - we still have a potential ability to perceive an invalid entry.

So I think I rescind my comment, lets do the non-atomic design, because it's "better than nothing" but cache redesign is probably on the cards sooner than later. :)

I have a doubt we should rely on the timestamp (to determine all updated entries to clear) because system time can change during a TXN.
On replicated environment we could rely on original CSN.

According to the comment on top of the struct, backentry/backcommon should be identical up to ep_size. Should not we add ep_create_time and ep_invalid before ep_size ?

I have a doubt we should rely on the timestamp (to determine all updated entries to clear) because system time can change during a TXN.
On replicated environment we could rely on original CSN.

I haven't reviewed and read all of the comments, so just jumping in. I think the EC ocntains entres adde with and without being transacted, so in case of searches adding entries you don't have a CSN, and then would need to decide if to remove them or not.
And it should be a rare condition having a tranasction aborted because of a plugin failure AND setting back system time, maybe we can just take the risk

I have a doubt we should rely on the timestamp (to determine all updated entries to clear) because system time can change during a TXN.
On replicated environment we could rely on original CSN.

But here we just set the montonic time when we add an entry to the cache. Are you worried someone will change the system time intentionally in between a operation failing and the server purging the cache when it fails? That is a very small window.

According to the comment on top of the struct, backentry/backcommon should be identical up to ep_size. Should not we add ep_create_time and ep_invalid before ep_size ?

What that really means is that both structs need to be identical for the common/shared elements. So in this case the comment should be changed to say "they need to be identical up to ep_create_time".

I have a doubt we should rely on the timestamp (to determine all updated entries to clear) because system time can change during a TXN.
On replicated environment we could rely on original CSN.

I haven't reviewed and read all of the comments, so just jumping in. I think the EC ocntains entres adde with and without being transacted, so in case of searches adding entries you don't have a CSN, and then would need to decide if to remove them or not.

I'm not using CSN's, I'm just taking the monotonic clock time when we start an operation and when an entry is added to the cache.

What that really means is that both structs need to be identical for the common/shared elements. So in this case the comment should be changed to say "they need to be identical up to ep_create_time".
I agree, I was initially thinking that the struct could be copy up to ep_size offset. But it is only used with pointer, so changing the comment is enough.

I've reverted the patch back to using ep_state for tracking invalid entries, and I fixed the comments in back-ldbm.h about the shared struct elements.

Please review...

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0

instead of 'entry' why not using 'laste'

Would it be possibly to simply set the state to ENTRY_STATE_INVALID, whether or not refcnt is 0.
Any access to an invalid entry would be ignored and we can let the LRU do its refcnt jobs.

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?

Is it still use ?

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0

You are correct, but we need to explicitly remove it because it does not get flushed from the LRU otherwise, and at shutdown the server silently crashes because the backend entry was already freed.

instead of 'entry' why not using 'laste'

Because laste is a void pointer and can not be dereferenced

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?

It's already checked in the cache find function because the ep_state is not 0

Is it still use ?

Looks like pagure did not put this comment in the diff view. What are you referring to?

Would it be possibly to simply set the state to ENTRY_STATE_INVALID, whether or not refcnt is 0.
Any access to an invalid entry would be ignored and we can let the LRU do its refcnt jobs.

I set the flag regardless of the refcnt and the tests still pass. (but I need to keep the remaining code or things start to fail or crash)

PR is rebased...

I've reverted the patch back to using ep_state for tracking invalid entries, and I fixed the comments in back-ldbm.h about the shared struct elements.
Please review...

Thanks mate, sorry for the run around :(

Is it still use ?

Looks like pagure did not put this comment in the diff view. What are you referring to?

I was referring to the enum type 'CacheType'

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0

You are correct, but we need to explicitly remove it because it does not get flushed from the LRU otherwise, and at shutdown the server silently crashes because the backend entry was already freed.

I think the backend entry should not be freed by the flush_hash. flush_hash sould only set it to invalid state. Sooner or later, the entry will be on the LRU (refcnt=0) and if there is need to reduce cache memory footprint then the LRU will free it.
The only thing is to make sure that lookup of the entry (find_hash) will not return an entry in invalid state

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?

It's already checked in the cache find function because the ep_state is not 0

You are right.
Each time we call find_hash we are testing the ep_state of the returned entry to ignore the entry if its ep_state is not 0.
you may also move this test inside find_hash.

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0
You are correct, but we need to explicitly remove it because it does not get flushed from the LRU otherwise, and at shutdown the server silently crashes because the backend entry was already freed.

I think the backend entry should not be freed by the flush_hash. flush_hash sould only set it to invalid state. Sooner or later, the entry will be on the LRU (refcnt=0) and if there is need to reduce cache memory footprint then the LRU will free it.

But that never happens. Just marking it invalid does not work in the case the refcnt is already zero. If I don't free it exactly they way I do it all kinds of things break. Tests fail and the server crashes at shutdown.

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?
It's already checked in the cache find function because the ep_state is not 0

You are right.
Each time we call find_hash we are testing the ep_state of the returned entry to ignore the entry if its ep_state is not 0.
you may also move this test inside find_hash.

Umm it does do this check in find_hash(), are you referring to a different function?

Is it still use ?
Looks like pagure did not put this comment in the diff view. What are you referring to?

I was referring to the enum type 'CacheType'

This was one of @firstyear requests

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0
You are correct, but we need to explicitly remove it because it does not get flushed from the LRU otherwise, and at shutdown the server silently crashes because the backend entry was already freed.
I think the backend entry should not be freed by the flush_hash. flush_hash sould only set it to invalid state. Sooner or later, the entry will be on the LRU (refcnt=0) and if there is need to reduce cache memory footprint then the LRU will free it.

But that never happens. Just marking it invalid does not work in the case the refcnt is already zero. If I don't free it exactly they way I do it all kinds of things break. Tests fail and the server crashes at shutdown.

The issue why just setting it invalid doesn't work is because the entry was already returned to the cache. Then looking for it never finds it again because it is invalid, and it's never removed from the cache or LRU once its invalid. So we have to do the purge ourselves in this case where it already has a refcount of zero. To do what you want requires a bit of hacking of other cache functions and to be honest feels a little riskier. I will see if I can get it to work, but I'm worried it will get a bit messy (we'll see)...

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?
It's already checked in the cache find function because the ep_state is not 0
You are right.
Each time we call find_hash we are testing the ep_state of the returned entry to ignore the entry if its ep_state is not 0.
you may also move this test inside find_hash.

Umm it does do this check in find_hash(), are you referring to a different function?

Oh ? sorry I do not see that test in find_hash(). Do you mean it is part of 'testfn' callback ?

I would expect 'laste' (or 'entry') to already be on the lru. Is on LRU all entries with refcnt==0
You are correct, but we need to explicitly remove it because it does not get flushed from the LRU otherwise, and at shutdown the server silently crashes because the backend entry was already freed.
I think the backend entry should not be freed by the flush_hash. flush_hash sould only set it to invalid state. Sooner or later, the entry will be on the LRU (refcnt=0) and if there is need to reduce cache memory footprint then the LRU will free it.
But that never happens. Just marking it invalid does not work in the case the refcnt is already zero. If I don't free it exactly they way I do it all kinds of things break. Tests fail and the server crashes at shutdown.

The issue why just setting it invalid doesn't work is because the entry was already returned to the cache. Then looking for it never finds it again because it is invalid, and it's never removed from the cache or LRU once its invalid. So we have to do the purge ourselves in this case where it already has a refcount of zero. To do what you want requires a bit of hacking of other cache functions and to be honest feels a little riskier. I will see if I can get it to work, but I'm worried it will get a bit messy (we'll see)...

In my mind I wanted to simplify the fix, letting the LRU free the entry when it has the opportunity to do so.

The LRU is a list of entries that are still in the hash but with refcnt=0.
find_hash can find the invalid entry but do not return it, the entry will stay in the LRU.
Later when the LRU will need some memory it will just remove the entry from the hash and free it.

It looks like 'find_hash' can return an entry even if it is state_invalid. Should it test the state and do not return the entry even if it finds it in the hash ?
It's already checked in the cache find function because the ep_state is not 0
You are right.
Each time we call find_hash we are testing the ep_state of the returned entry to ignore the entry if its ep_state is not 0.
you may also move this test inside find_hash.
Umm it does do this check in find_hash(), are you referring to a different function?

Oh ? sorry I do not see that test in find_hash(). Do you mean it is part of 'testfn' callback ?

Sorry it's in cache_find_id()

I think you should not test INVALID at the point, and just let the entry go in the LRU (lru_add)

With offline discussion/test, the solution I was thinking about (let the LRU remove/free the invalid entry) is still giving a entry cache corruption.

About the idea to move the test of ep_state into find_hash, it is not possible because find_hash does not know the structure of the entry.

Thanks Mark for your patience. You have my ACK

For the record, you have my ack too :)

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This pull request has been cloned to Github as issue and is available here:
- https://github.com/389ds/389-ds-base/issues/3328

If you want to continue to work on the PR, please navigate to the github issue,
download the patch from the attachments and file a new pull request.

Thank you for understanding. We apologize for all inconvenience.