Pandora PND diffs


_wb_

Microbe
Staff member
Joined
Apr 5, 2012
Messages
5,390
Age
42
Location
Brussels, Belgium
From this thread: http://boards.openpandora.org/index.php/topic/13088-some-repo-statistics-for-you/

Looking at the massive bandwidth use, I wonder if using a diff to update a pnd instead of downloading the whole pnd would be viable
Something like this should work:

Server-side:

When a PND gets uploaded that already existed (so it's an update), if the PXML contains something specific to allow incremental updates, then unpack both the current version and the most recent archived version. Create a list of all modified, added or deleted files, and put the modified or added files, together with the list of deleted files and maybe some other meta-data, in a .tar.bz2 (you could also do more detailed diffs but since most files will be binaries, that will probably not be worth the effort). You could include a checksum of the full PND in this meta-data, as well as instructions on how the PND has to be created (compressed or not? what icon? basically the parameters to pnd_make.sh). Make both the full PND and the incremental update .tar.bz2 available for download.

Client-side:

Make a shell script that takes an old PND and an update .tar.bz2, unpacks the PND, copies the files from the .tar.bz2 and removes the files to be removed, repacks the PND according to the instructions in the metadata, and checks the checksum to verify that everything went well.

Add an automated feature in PNDManager to download the incremental update instead of the full PND and call the shell script.

You could also allow authors to upload the diff instead of the full PND, which would be really useful if you want to do stuff like edit the PXML a bit or add some screenshots without having to reupload the entire thing again.

Anyone sufficiently fluent in bash (or whatever) to make something like this?

Basically we need a tool


pnd_diff <OLD_PND> <NEW_PND> <DIFF_FILE>
and a tool


pnd_merge <OLD_PND> <DIFF_FILE> <NEW_PND>
where in both cases, the first two arguments are input files and the last one is the output.
 
Last edited by a moderator:
I toyed with that idea a few years ago.

The problem is that PND are mostly squashfs files. So it's binary data and the compression algorythm make it very hard to get a clean diff (try to diff 2 revisions of any of your own PND)

An idea would be to mount both PND and diff the PND content then compress the end result.

The problem with this idea is : how to merge on pandora? To merge you'll need to extract the current PND somewhere, apply the diff and create a new PND out of this. This operation _requiere_ a Unix FS. You cannot expect the SDcard to be something else than a vfat FS and there isnt enough room in the NAND to do so.

So either you might create patches larger than the final PND or you cannot merge. I stopped toying that idea at that point....
 
Can't you just mount the original PND but without the appdata overlay, have an overlay in tmpfs for the diff (in tmpfs to make sure that you have a unix fs), and use that to produce the merged PND?

That still means that the diff has to fit in RAM, but that shouldn't be a big problem: the diff should be small compared to the PND itself, otherwise there's no point to do this.
 
I toyed with that idea a few years ago.

The problem is that PND are mostly squashfs files. So it's binary data and the compression algorythm make it very hard to get a clean diff (try to diff 2 revisions of any of your own PND)

An idea would be to mount both PND and diff the PND content then compress the end result.
Recompression might not give you identical file (depends on squashfs-tools version and args), and I wouldn't like my releases to be not 100% the same what I have built and tested.

Squashfs shouldn't be making the whole stream different when just a few files change in the archive, because it has to be able access files fast in the archive, files should be compressed separately there. I think someone mentioned rsync is very efficient when working with these files, so there should be identical blocks there, only offset differently.

If it's really true rsync is good at this (haven't verified it myself), it would probably best to have a tool that uses rsync algorithm to make a diff file.

Actually similar problems are faced by ROM hacking community too, so maybe things like IPS patching would work too. I think there are several other binary patching tools that could be checked if they work well on squashfs.
 
Last edited by a moderator:
I'm assuming you can mount PND's squashfs for write as well as read. Could you do an "Upgrade PND" which contains any updated files (including the PXML), and the updater mounts both PNDs, and transfers the newer files into the old one, unmounts, then updates the PXML?

Edit: Or even the updater PND has a bunch of diffs for each binary that it applies, along with a list of new files to add, and a list of files to remove
 
Last edited by a moderator:
I'm assuming you can mount PND's squashfs for write as well as read.
Squashfs and ISOfs are strictly readonly.
Hmmm, that's a bit of a bummer, I guess the only way around that would be to mount the original, and create a new SquashFS mixing the mounted data plus the upgrade data, but that seems like overkill.
There's a bit in section 4.4 here, about making SquashFS writable using UnionFS? Would that be of any use?
 
I think this is overly complex for very little gain since for most people bandwidth is not a problem, plus as @notaz already said if it isn't done right he might get people asking for help with his pnd because its not the same as the one he tested.
 
I guess you'd also have to cater for diffs between multiple version.

Still this thread might help with a design for a PND plugin type system?
 
There's a bit in section 4.4 here, about making SquashFS writable using UnionFS? Would that be of any use?
That's pretty much how the PND system manage the appdata ;) But that's not a way to create a newer PND

On the topic. Yet an other solution, would be use patches at runtime :

1) mount the PND

2) mount the patch if found (a squashfs file, might want to check if the versions match too)

3) mount the appdata

4) play the app

This one also have a few limits :

- Theses patches would be manually created

- Theses patches cannot be cumulatives (Im not seeing a sane way to mount 5-10 overlays)
 
So let's go for binary diffs like notaz and me propose. It is simple to implement (no need to unpack PNDs or mount overlays or anything like that), and it ensures that you get a PND that is identical to the target one.

@milkshake: bandwidth is actually a real problem for some people, and even if you have plenty of bandwidth, the pandora wifi is not always that reliable so if we can somehow make some of the updates more efficient, that will help a lot.
 
So let's go for binary diffs like notaz and me propose. It is simple to implement (no need to unpack PNDs or mount overlays or anything like that), and it ensures that you get a PND that is identical to the target one.
How are you planning on dealing with multiple version changes? I'm assuming your diffs will only be between the "last version" and the "current version"?
 
Hows about giving the currently installed version number to the repo, manually or automatically,  which creates a diff (or fetches it from cache) and provides a download.
 
The International Patch System (mentioned by Notaz) apparently has the ability to track not just in-place changes, but also "moves" and "expansions". If you change just a single file in a squashfs, based on anecdotal reports about rsync, it would appear that all it does is change the compressed data associated with that block: every other file should be recompressed the same way, just possibly in a different position within the file. Take the old PND and the new PND, create an IPS patch from them, transfer the patch, apply the patch locally. The total amount of data transfered should be no more than the size of the file(s) that changed within the PND. If you've got a game with a 2MB binary and 28MB of static data, in theory you could save 93% of the bandwidth and transfer time when just the binary changes.

edit: another benefit of IPS is that it's cumulative, you can keep patches between versions and upgrade a bunch one after the other to get to the most recent revision.

Some tweaks would need to be done for our particular use case, but this is actually sounding a lot more plausible. I'll see if I can create some quick tests.
 
Last edited by a moderator:
Upon further inspection, it looks like the PPF format would work: it's actually designed with ISO file patching in mind, which may translate to squashfs. I just need to find a tool which can create PPF files.
 
Back
Top