Beware that this post is related to an SDK in maintenance mode
More Info: Consider nRF Connect SDK for new designs
This post is older than 2 years and might not be relevant anymore
More Info: Consider searching for newer posts

FDS read order (fds_record_find) doesn't reflect write order (fds_record_write) for multiple records with same record_key and file_id, if virtual page boundaries are crossed

The assumption that `fds_record_find` returns records for NOT CHANGING file_id and record_key in the same
order they have been written IS WRONG.

The documentation sub-section "storage format" of FDS states the following:

```
Record layout

Records consist of a header (the record metadata) and the actual content. They are stored contiguously in flash in
the order they are written.
```

It turns out that this rule doesn't apply if virtual page boundaries are crossed.
The behavior seems to be the following:

If a record should be written but a virtual page couldn't take it (because the virtual page has too few space left)
it is written to the next virtual page with enough remaining space. If a successive operation tries to write a
smaller record, which still fits into the virtual page which couldn't be used for the first write (the last record
was too large, but this one fits) this record is written to the virtual page preceding the one used for the first
fds_record_write call. From fsstorage perspective, this means that these two records aren't layed out in write order,
because they are swapped.

Now the `fds_record_find` method follows a simple logic, if multiple records with same file_id and record_id should
be returned. It steps through each virtual page (in order) and for each virtual page it steps through all records and
returns the next record (according to the find_token), which matches the filter criteria (file_id and record_key).
For the example above, the iteration would hit the record which was written in the second call to `fds_record_write`
FIRST, because it was stored in the virtual page preceding the virtual page of the first call to fds_record_write.

This means if order of data is critical, different record_key (e.g. incrementing) or file_ids have to be used.
Records with same file_id and record_key have to be seen as "set" where read order (fds_record_find) isn't guaranteed
to reflect write order (successive calls to fds_record_write).

Note 1: Increasing virtual page size for FDS could mitigate the problem, but it still occurs if page boundaries are
crossed for records with same file_id and record_key.

Note 2: Not waiting for write operations to finish isn't part of the problem described here, as it was assured that
no successive `fds_record_write` calls have been enqueued, before the respective FDS_EVT_WRITE occurred.


The documentation of FDS isn't clear on the question if read order should align to write order (for records with
same record key and file ID), but at least that is the expected behavior IMO.

I can't provide stripped down sample code to reproduce it. The problem occured in one of my projects, source with affected
code could be found here:

https://github.com/mame82/LOGITacker/blob/master/logitacker/logitacker_script_engine.c#L554

--> `logitacker_script_engine_store_current_script_to_flash` stores multiple records with same record_key and file_id

where order is important (distinguishing header and data records)

--> `logitacker_script_engine_load_script_from_flash` reads back those record and relies on order (to distinguish header

records from data records)

In my case, the problem could be solved by using incremental record_keys. If this is an requirement, because multiple records

with same record_key and file_id not preserved order is intended, it should at least be pointed out in the documentation.

  • Hi,

    Thank you for the detailed report. It is highly appreciated!

    I am happy to report that the documentation is changed for next nRF5 SDK release, covering the situation you describe.

    Regarding distinguishing header and data records, a better approach might be to use e.g. one File ID for headers and one File ID for data, and map the two using Record key as index. Or, if header is of fixed size, to store header and data in the same record.

    Regards,
    Terje

  • Hi Terje,

    thank you for the fast reply and taking care of this.

    Considering the suggestions:

    - using dedicated file_id entries for header/data records would assure that header records and data records couldn't get swapped. But it wouldn't solve the whole problem, because still wrong order isn't preserved (data record could be applied to wrong header record, if order for either element is changed)

    - merging the header (yes fixed size) and data into a single record, still wouldn't assure correct order of the merged records. This is critical for my use case, as the records represent sequential tasks in a script (task order is of importance).

    Logical representation of those tasks at runtime is a TLV struct. Flash layout basically stores Type+Data Length in one record (fixed size header). The actual (dynamic size) data is stored in a ringbuffer at runtime. Merging it before writing would force me to use an additional "merge array"  which is preserved till flash writes are finished, which constantly consumes additional RAM (has to be static).

    Working solution for my use case:

    File_ID is chosen dynamically to represent a logic group of records (a script). For storage of individual script tasks (each consisting of a fixed size header record and a dynamic size data record) the record_key is incremental for each call to fds_record_write (initial ID is the same for all scripts, which still could be distinguished by file_id).

    For reading back, fds_record_find us called with the file_id of the intended script and the initial record_key. For each call to fds_record_find, the record_key is incremented and the find_token reset to {0} (to assure search hits all virtual pages).

    This assures that each call to fds_record_find returns the correct record, no matter if order was changed at virtual page boundaries.

  • HI,

    I am glad to hear that you have a working solution. (I suspected you were in full control, and apparently you were.)

    I can think of a couple of other reasons for why the ordering can differ as well. The first one is garbage collection, during which valid records from the page being garbage collected are (persistently) moved to the swap page. The second one is after garbage collection, at which point data pages are typically part empty, and so collections of old records (at beginning of each data page) gets "zipped" with new records (at end of each data page).

    Both of the above sources of mis-ordering are of course mitigated by your solution.

    What still holds true, is that the valid records within a virtual flash page are sorted with respect to time of writing. Records overall, however, are not. Order is not kept across virtual page boundaries, and the records within one virtual page are not necessarily a continuous series of records.

    Regards,
    Terje

Related