search

eerimoq / detools

Binary delta encoding tools.
Other
157 stars 16 forks source link

In-place patching: Minimising the number of fwrite calls #11

Closed Harshal5 closed 1 year ago

Harshal5 commented 1 year ago

Hello @eerimoq,

I am trying to investigate the integration of detools in an embedded systems project, where I need an in-place patching mechanism.

We are using an SPI (NOR) flash memory and the "flash" writes a whole binary (.bin) file on it. To write a new binary file on it, we were thinking of using the diff in-place patching mechanism provided by detools rather than the orthodox way of writing the whole new binary file.

Our main objective behind this is to reduce the number of fwrite calls needed. Below are the results of a basic analysis I carried out to check the number of fwrite calls needed in an in-place operation:

Created two in_place patches, one with minimum shift size 0 (patch size = 93179 B) and another with default minimum shift size (2*segment_size) (patch size = 11715 B).

(from_file size = 176128 B, to_file size = 174624 B.)

memory size segment size minimum shift size number of fwrite counts
176128 4096 0 4419
176128 4096 8192 2712

(number of fwrite counts was counted by adding a static count variable here)

I had the following questions regarding the same:

  1. Is there a way to reduce the number of fwrite counts? (probably writing just the diff data segments)
  2. I thought one way of reducing the fwrite counts could be by not shifting the memory by minimum-shift-size bytes (ref). Does changing the minimum shift size to 0 make sure that the initial memory shifting does not take place?
  3. Though I tried doing so, surprisingly I found the number of fwrite counts increased. (Or why does the patch size increase when the minimum shift size is 0 (patch size = 93179 B) as compared to when the minimum shift size is 8192 B (patch size = 11715 B) ?)

Could you please help me answer these questions? Also, please do let me know about any suggestions for this integration in my case.

eerimoq commented 1 year ago

The bsdiff algorithm that is used to create in-place patches is not trivial to modify to minimize the number of fwrites. To get the lowest number of fwrites you should write the .bin as is, and not creating a patch. Patches are by nature moving lots of data around.

Harshal5 commented 1 year ago

Got it. Thank you for the reply. Closing this issue.