This issue occurred with the #5323 PR enabled to use ordered dict/map by default everywhere, hence the ordered implementation was being used in asyncio/uselect

Thanks for the PR. Are you able to provide a pure Python test that shows the issue with map and ordered dicts?

Regarding the second commit that changes uasyncio: I'm not sure that's good to merge at this point, probably it needs it's own PR to discuss (it allocates memory...). And I think that issue would anyway be fixed by #6125 (replacing uselect with uevent).

@dpgeorge yep! Happy to do that. Is it worth me re-raising, or are you pretty confident that the uevent will fix it? (I'm just conscious of not wasting your time with it's review if there's another big change already in flight).

Is it worth me re-raising, or are you pretty confident that the uevent will fix it?

I'm pretty confident uevent will fix the issue, because it internally unregisters IO objects when they no longer have any events pending.

I've dropped the uasyncio changes.

I haven't found a way to put together a python-level test case, unfortunately. All other consumers of map immediately replace the exposed value (for example, objdict), thereby avoiding the issue that uselect encounters. Given you're about to replace uselect wholesale, it's unlikely that a test showing the bug here would add much value in the long term.

The visual inspection with relation to unordered maps make it reasonably trivial to verify that the fix is correct. Is there an accepted way to write a lower-level C test against the map interface for this?

On its own I don't think the patch here fixes anything. Using always-ordered dicts with uasyncio is just not going to work, and this patch alone will not fix it (but correct me if I'm wrong).

This test code:

// Add a key that will cause an allocation
mp_map_elem_t *elem = mp_map_lookup(poll_map, mp_obj_id(obj_in), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);
elem->value = 100; // Set a value for us to discover later

// Now remove the new key
mp_map_lookup(&self->poll_map, mp_obj_id(obj_in), MP_MAP_LOOKUP_REMOVE_IF_FOUND);

// And add it back again
mp_map_elem_t *elem2 = mp_map_lookup(poll_map, mp_obj_id(obj_in), MP_MAP_LOOKUP_ADD_IF_NOT_FOUND);

// When the bug is present, the value returned will be identical, though it should be MP_OBJ_NULL)
assert(elem->value != elem2->value)

it doesn't use the map API correctly: after calling mp_map_lookup(.., MP_MAP_LOOKUP_REMOVE_IF_FOUND) the caller must set elem->value = MP_OBJ_NULL, as mentioned in the comment in py/map.c. Doing that would probably mean the patch here is not needed. Also, mp_map_elem_t* pointers are not valid after another call to map_map_lookup() which modifies the map, so the last assert doesn't really make sense.

In summary: I don't think there is any bug to fix here (although the fix itself doesn't hurt).

Sounds like my C example as slightly off. You are correct that you'd need to deref and store elem->value to make it valid, but the point still stands. It will return the old value in the re-used slot.

My key point is:

There is an obvious inconsistency within the map implementation, with regards to calling mp_map_lookup with MP_MAP_LOOKUP_ADD_IF_NOT_FOUND when a slot is reused.

• When the collection is not ordered, mp_map_lookup will set the slot value to MP_OBJ_NULL before returning it back to the caller. I should note, this behaviour is consistent across the other 3 locations I linked in the existing code.
• However, when the collection is ordered, there was no call to reset the slot value, hence this patch. This is the only call that fails to reset the value in the returned slot.

Regarding the compatibility with uasyncio, you'll obviously know better than me.

Are you saying that uasyncio is relying on undefined behaviour by checking if the returned element value is MP_OBJ_NULL to determine whether the key already existed in the map?

You are correct that there is one other issue remaining with uasyncio with regards to modifying the map while iterating over it. However, I believe that is orthogonal to the inconsistency within the map implementation when comparing the API behaviour for ordered vs unordered maps.

(The iteration issue in uasyncio also has a relatively straightforward fix, but we're just choosing to leave it alone as you are planning to replace the uselect module soon with the new uevents stack, if I'm not mistaken?)

I've got a way to show the issue from python code with a one-line change to objdict. Note, the existing objdict itself doesn't show this issue, because it always clears the return slot itself... so, I'm not suggesting there is an existing python-accessible bug with the dict.

This python code, comparing the behaviours with an ordered vs. normal dict:

for d in [dict(), OrderedDict()]:
    print("\n\n===", type(d), "===")
    d[10] = "value"
    print("popping key 10")
    d.pop(10)
    print("setting default value for key 10 (should be not present in map)")
    result = d.setdefault(10, "new value")
    print(result, "==", "new value", "?", (result == "new value"))

Combined with this tweak to objdict.c in the dict_get_helper method (specifically, removing the re-nulling that happens when lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND):

STATIC mp_obj_t dict_get_helper(size_t n_args, const mp_obj_t *args, mp_map_lookup_kind_t lookup_kind) {
    mp_check_self(mp_obj_is_dict_type(args[0]));
    mp_obj_dict_t *self = MP_OBJ_TO_PTR(args[0]);
    if (lookup_kind != MP_MAP_LOOKUP) {
        mp_ensure_not_fixed(self);
    }
    mp_map_elem_t *elem = mp_map_lookup(&self->map, args[1], lookup_kind);
    mp_obj_t value;
    if (elem == NULL || elem->value == MP_OBJ_NULL) {
        printf("objdict.c:dict_get_helper| inserting new value\n"); // <-- added this line
        if (n_args == 2) {
            if (lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
                nlr_raise(mp_obj_new_exception_arg1(&mp_type_KeyError, args[1]));
            } else {
                value = mp_const_none;
            }
        } else {
            value = args[2];
        }
        if (lookup_kind == MP_MAP_LOOKUP_ADD_IF_NOT_FOUND) {
            elem->value = value;
        }
    } else {
        printf("objdict.c:dict_get_helper| found existing value in slot\n"); // <-- added this line
        value = elem->value;
        if (lookup_kind == MP_MAP_LOOKUP_REMOVE_IF_FOUND) {
            // elem->value = MP_OBJ_NULL; // so that GC can collect the deleted value // <-- commented out this line to show API difference
        }
    }
    return value;
}

Or as a screenshot to show the diff:

The output the python test produces is:

=== <class 'dict'> ===
popping key 10
objdict.c:dict_get_helper| found existing value in slot
setting default value for key 10 (should be not present in map)
objdict.c:dict_get_helper| inserting new value
new value == new value ? True


=== <class 'OrderedDict'> ===
popping key 10
objdict.c:dict_get_helper| found existing value in slot
setting default value for key 10 (should be not present in map)
objdict.c:dict_get_helper| found existing value in slot
value == new value ? False

I would expect the output to be identical for both dictionaries, but as can clearly be seen, when using the OrderedDict type, setdefault incorrectly finds an existing value.

Once my patch here is applied, this discrepancy is removed.

To repeat, there is no bug at the python level (apart from when uselect is used with globally ordered dictionaries)... but there is a clear difference with the lower level mp_map_lookup behaviour when using ordered vs. unordered maps.

On a side note, it looks like basically each map consumer throughout the codebase already has this output value (re-)nulling in place (except uselect), which if this PR is applied means it's duplicate code sprinkled throughout the codebase that could be cleaned up to save a few bytes of flash.

Revisiting this (with fresh eyes!) I see that it is indeed needed, because the comment for mp_map_lookup() says:

// MP_MAP_LOOKUP_ADD_IF_NOT_FOUND behaviour:
//  - returns slot, with key non-null and value=MP_OBJ_NULL if it was added

Code size report:

   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000%