Change bsdiff's suffix sort algorithm to sais. Fixes #132#515
Merged
kornelski merged 1 commit intosparkle-project:masterfrom Apr 5, 2015
Merged
Change bsdiff's suffix sort algorithm to sais. Fixes #132#515kornelski merged 1 commit intosparkle-project:masterfrom
kornelski merged 1 commit intosparkle-project:masterfrom
Conversation
Although sparkle-project#132 is marked as closed, the issue is still real. bsdiff can crash or hang when creating diffs on some files. In particular, bsdiff hangs/crashes in its recursive split function. As you can see from: http://stackoverflow.com/a/20305493/871119 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 bsdiff 4.3 uses qsufsort for its suffix sorting algorithm, which has a bug causing the hanging/crashing. Our solution is to change the algorithm to use sais for suffix sorting: https://sites.google.com/site/yuta256/sais Notes: *I had to change sais_index_type #define from int to off_t in sais.h/c and in some other places, to eliminate all warnings. Compiles cleanly with clang's -Weverything *sais is claimed to be more efficient than other algorithms including qsufsort. If a more efficient (and stable) algorithm comes out, we may be able to swap it out in the future.
Member
|
Thanks for the fixes. It's curious that the issue hasn't been fixed upstream. There's a fork with a PR with sais as well but unfortunately it's not compatible. …which makes me wonder, is this modification backwards-compatible with existing diffs? |
Member
Author
|
Hm, that's interesting. Looks like the PR request for that repo got their fix idea from the same person I did in that Stack Overflow thread. That fork of bsdiff is not intended to be compatible with the original bsdiff version that we use, which is not related to using sais. My pull request shouldn't require changes to bspatch. |
kornelski
added a commit
that referenced
this pull request
Apr 5, 2015
Change bsdiff's suffix sort algorithm to sais. Fixes #132
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 14, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 15, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 15, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 15, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 16, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 16, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 16, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 16, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 17, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 17, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 17, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 20, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 21, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 22, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 22, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 22, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 22, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 22, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 23, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 23, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 29, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 29, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
glevand
added a commit
to glevand/coreos--coreos-overlay
that referenced
this pull request
Jul 30, 2015
To avoid dependencies on dev-libs/libdivsufsort and dev-util/cmake convert bsdiff from using the divsufsort suffix sort to using the sais-lite suffix sort from [1]. The need for an alternative suffix sort is discussed in [2] through [4]. A dependency on dev-util/cmake is problematic as cmake cannot be cross-compiled and a switch to sais-lite avoids this dependency. [1] https://sites.google.com/site/yuta256/sais [2] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664 [3] sparkle-project/Sparkle#515 [4] https://chromium.googlesource.com/chromiumos/third_party/bsdiff/+/e2b85ce4ea246ca804ee2a9e18005c44e193d868 Signed-off-by: Geoff Levand <geoff@infradead.org>
6 tasks
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Although #132 is marked as closed, the issue is still real. bsdiff can crash or hang when creating diffs on some files. In particular, bsdiff hangs/crashes in its recursive split function.
As you can see from:
http://stackoverflow.com/a/20305493/871119
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=409664
bsdiff 4.3 uses qsufsort for its suffix sorting algorithm, which has a bug causing the hanging/crashing. Our solution is to change the algorithm to use sais for suffix sorting:
https://sites.google.com/site/yuta256/sais
Notes:
I'll start to look into writing actual tests soon. Going through other people's issues/tests just seems to prioritize higher ;).