Debian Bug report logs - #719845
dpkg-deb: Make file order within {data,control}.tar.gz deterministic

Toggle useless messages

Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: Asheesh Laroia <asheesh@asheesh.org>

To: submit@bugs.debian.org

Subject: dpkg-source: Make file order within {data,control}.tar.gz deterministic

Date: Thu, 15 Aug 2013 19:46:25 -0400 (EDT)

Package: dpkg
Version: 1.16.10
Severity: normal

*** Please type your report below this line ***

Summary: To move toward https://wiki.debian.org/ReproducibleBuilds for 
maintainers who want their binary packages to be able to be reproduced 
bit-for-bit, it would be needed for dpkg to sort the files before adding 
them to the tar files of {data,control}.tar.{xz,bz2,gz}.

That way, the creation of the data.tar.gz would be deterministic.

Message #10 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Guillem Jover <guillem@debian.org>

To: Asheesh Laroia <asheesh@asheesh.org>, 719845@bugs.debian.org

Subject: Re: Bug#719845: dpkg-source: Make file order within {data,control}.tar.gz deterministic

Date: Fri, 16 Aug 2013 08:53:21 +0200

Control: severity -1 wishlist

Hi!

On Thu, 2013-08-15 at 19:46:25 -0400, Asheesh Laroia wrote:
> Package: dpkg
> Version: 1.16.10
> Severity: normal
> 
> Summary: To move toward https://wiki.debian.org/ReproducibleBuilds
> for maintainers who want their binary packages to be able to be
> reproduced bit-for-bit, it would be needed for dpkg to sort the
> files before adding them to the tar files of
> {data,control}.tar.{xz,bz2,gz}.
> 
> That way, the creation of the data.tar.gz would be deterministic.

Indeed, that's something that has been on the back of my mind for some
time now, and that I was/am planning on fixing during the 1.17.x cycle.
This will also be part of a two step process to guarantee the dpkg
database is also more deterministic, dpkg would need to sort
(preserving symlinks at the end) the files when dumping them on the
database (to cater for older unsorted debs).

Thanks,
Guillem

Message #17 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Asheesh Laroia <asheesh@asheesh.org>

To: Guillem Jover <guillem@debian.org>

Cc: 719845@bugs.debian.org

Subject: Re: Bug#719845: dpkg-source: Make file order within {data,control}.tar.gz deterministic

Date: Fri, 16 Aug 2013 08:58:52 -0400 (EDT)

On Fri, 16 Aug 2013, Guillem Jover wrote:

> Indeed, that's something that has been on the back of my mind for some
> time now, and that I was/am planning on fixing during the 1.17.x cycle.
> This will also be part of a two step process to guarantee the dpkg
> database is also more deterministic, dpkg would need to sort
> (preserving symlinks at the end) the files when dumping them on the
> database (to cater for older unsorted debs).

Awesome.

I am thrilled that this is already on your radar, and the "generally 
during this cycle" time-frame is completely satisfying.

Message #24 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Shawn Landden <shawnlandden@gmail.com>

To: debian-dpkg@lists.debian.org, 719845@bugs.debian.org

Cc: Shawn Landden <shawnlandden@gmail.com>

Subject: [PATCH] convert file_info from singlely-linked list to rbtree

Date: Thu, 22 Aug 2013 12:16:33 -0700

now filenames are sorted via tree-sort to increase determinism in builds

lookup (was only used in check_conffiles()) is now O(log(n)) instead
of O(n)

The license of libtree is a bit funny: _Library_ GPL _2_ (which doesn't exist)
I have asked upstream for clarification on this:

https://github.com/fbuihuu/libtree/issues/7
---
 dpkg-deb/Makefile.am |   1 +
 dpkg-deb/build.c     | 110 ++++++------
 dpkg-deb/libtree.h   | 218 +++++++++++++++++++++++
 dpkg-deb/rb.c        | 485 +++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 760 insertions(+), 54 deletions(-)
 create mode 100644 dpkg-deb/libtree.h
 create mode 100644 dpkg-deb/rb.c

diff --git a/dpkg-deb/Makefile.am b/dpkg-deb/Makefile.am
index 6b66d3e..772c8c0 100644
--- a/dpkg-deb/Makefile.am
+++ b/dpkg-deb/Makefile.am
@@ -12,6 +12,7 @@ bin_PROGRAMS = dpkg-deb
 
 dpkg_deb_SOURCES = \
 	dpkg-deb.h \
+        rb.c \
 	build.c \
 	extract.c \
 	info.c \
diff --git a/dpkg-deb/build.c b/dpkg-deb/build.c
index 348e01e..061a237 100644
--- a/dpkg-deb/build.c
+++ b/dpkg-deb/build.c
@@ -52,12 +52,13 @@
 #include <dpkg/options.h>
 
 #include "dpkg-deb.h"
+#include "libtree.h"
 
 /**
  * Simple structure to store information about a file.
  */
 struct file_info {
-  struct file_info *next;
+  struct rbtree_node node;
   struct stat st;
   char *fn;
 };
@@ -69,11 +70,16 @@ file_info_new(const char *filename)
 
   fi = m_malloc(sizeof(*fi));
   fi->fn = m_strdup(filename);
-  fi->next = NULL;
+  /* fi->node uninitilized */
 
   return fi;
 }
 
+/**
+ * Frees a file_info struct
+ * 
+ * does NOT remove it from the rbtree, as this is used during rbtree destruction
+ */
 static void
 file_info_free(struct file_info *fi)
 {
@@ -82,13 +88,14 @@ file_info_free(struct file_info *fi)
 }
 
 static struct file_info *
-file_info_find_name(struct file_info *list, const char *filename)
+file_info_find_name(struct rbtree *tree, const char *filename)
 {
-  struct file_info *node;
+  struct file_info fi;
+  struct rbtree_node *r;
 
-  for (node = list; node; node = node->next)
-    if (strcmp(node->fn, filename) == 0)
-      return node;
+  fi.fn = (char *)filename;
+  if (r = rbtree_lookup(&fi.node, tree))
+    return rbtree_container_of(r, struct file_info, node);
 
   return NULL;
 }
@@ -132,39 +139,29 @@ file_info_get(const char *root, int fd)
   return fi;
 }
 
-/**
- * Add a new file_info struct to a single linked list of file_info structs.
- *
- * We perform a slight optimization to work around a ‘feature’ in tar: tar
- * always recurses into subdirectories if you list a subdirectory. So if an
- * entry is added and the previous entry in the list is its subdirectory we
- * remove the subdirectory.
- *
- * After a file_info struct is added to a list it may no longer be freed, we
- * assume full responsibility for its memory.
- */
-static void
-file_info_list_append(struct file_info **head, struct file_info **tail,
-                      struct file_info *fi)
+rbtree_cmp_fn_t file_info_compare(const struct rbtree_node *a, const struct rbtree_node *b);
+rbtree_cmp_fn_t
+file_info_compare(const struct rbtree_node *a, const struct rbtree_node *b)
 {
-  if (*head == NULL)
-    *head = *tail = fi;
-  else
-    *tail = (*tail)->next =fi;
+  struct file_info *p = rbtree_container_of(a, struct file_info, node);
+  struct file_info *q = rbtree_container_of(b, struct file_info, node);
+  
+  return strcmp(p->fn, q->fn);
 }
 
+
 /**
- * Free the memory for all entries in a list of file_info structs.
+ * Free the memory for all entries in a rbtree of file_info structs when passed
+ * the root node: (struct rbtree).root
  */
 static void
-file_info_list_free(struct file_info *fi)
+file_info_tree_free(struct rbtree_node *node)
 {
-  while (fi) {
-    struct file_info *fl;
-
-    fl=fi; fi=fi->next;
-    file_info_free(fl);
-  }
+  if (node->left)
+    file_info_tree_free(node->left);
+  if (node->right)
+    file_info_tree_free(node->right);
+  file_info_free(rbtree_container_of(node, struct file_info, node));
 }
 
 static const char *const maintainerscripts[] = {
@@ -225,8 +222,8 @@ check_conffiles(const char *dir)
   FILE *cf;
   struct varbuf controlfile = VARBUF_INIT;
   char conffilename[MAXCONFFILENAME + 1];
-  struct file_info *conffiles_head = NULL;
-  struct file_info *conffiles_tail = NULL;
+  struct file_info *conffile = NULL;
+  struct rbtree conffiles;
 
   varbuf_printf(&controlfile, "%s/%s/%s", dir, BUILDCONTROLDIR, CONFFILESFILE);
 
@@ -256,6 +253,7 @@ check_conffiles(const char *dir)
       continue;
     }
 
+    rbtree_init(&conffiles, file_info_compare, 0);
     conffilename[n - 1] = '\0';
     varbuf_reset(&controlfile);
     varbuf_printf(&controlfile, "%s/%s", dir, conffilename);
@@ -271,17 +269,15 @@ check_conffiles(const char *dir)
       warning(_("conffile '%s' is not a plain file"), conffilename);
     }
 
-    if (file_info_find_name(conffiles_head, conffilename)) {
-      warning(_("conffile name '%s' is duplicated"), conffilename);
-    } else {
-      struct file_info *conffile;
-
+    if (file_info_find_name(&conffiles, conffilename))
+      warning(_("conffile name '%s' is duplicated"), conffilename
+    else {
       conffile = file_info_new(conffilename);
-      file_info_list_append(&conffiles_head, &conffiles_tail, conffile);
+      rbtree_insert(&conffile->node, &conffiles);
     }
   }
-
-  file_info_list_free(conffiles_head);
+  if (conffiles.root)
+    file_info_tree_free(conffiles.root);
   varbuf_destroy(&controlfile);
 
   if (ferror(cf))
@@ -396,8 +392,8 @@ do_build(const char *const *argv)
   int p1[2], p2[2], p3[2], gzfd;
   pid_t c1,c2,c3;
   struct file_info *fi;
-  struct file_info *symlist = NULL;
-  struct file_info *symlist_end = NULL;
+  struct rbtree list;
+  struct rbtree symlist;
 
   /* Decode our arguments. */
   dir = *argv++;
@@ -575,24 +571,30 @@ do_build(const char *const *argv)
   close(p3[1]);
   /* We need to reorder the files so we can make sure that symlinks
    * will not appear before their target. */
+  rbtree_init(   &list, file_info_compare, 0);
+  rbtree_init(&symlist, file_info_compare, 0);
   while ((fi = file_info_get(dir, p3[0])) != NULL)
     if (S_ISLNK(fi->st.st_mode))
-      file_info_list_append(&symlist, &symlist_end, fi);
-    else {
-      if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
-        ohshite(_("failed to write filename to tar pipe (%s)"),
-                _("data member"));
-      file_info_free(fi);
-    }
+      rbtree_insert(&fi->node, &symlist);
+    else
+      rbtree_insert(&fi->node,    &list);
   close(p3[0]);
   subproc_wait_check(c3, "find", 0);
 
-  for (fi= symlist;fi;fi= fi->next)
+  for (fi= rbtree_container_of(rbtree_first(   &list),  struct file_info, node);fi;
+       fi= rbtree_container_of(rbtree_next(&fi->node), struct file_info, node))
+    if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
+      ohshite(_("failed to write filename to tar pipe (%s)"), _("data member"));
+  for (fi= rbtree_container_of(rbtree_first(&symlist), struct file_info, node);fi;
+       fi= rbtree_container_of(rbtree_next(&fi->node), struct file_info, node))
     if (fd_write(p1[1], fi->fn, strlen(fi->fn) + 1) < 0)
       ohshite(_("failed to write filename to tar pipe (%s)"), _("data member"));
   /* All done, clean up wait for tar and gzip to finish their job. */
   close(p1[1]);
-  file_info_list_free(symlist);
+  if (list.root)
+    file_info_tree_free(   list.root);
+  if (symlist.root)
+    file_info_tree_free(symlist.root);
   subproc_wait_check(c2, _("<compress> from tar -cf"), 0);
   subproc_wait_check(c1, "tar -cf", 0);
   /* Okay, we have data.tar as well now, add it to the ar wrapper. */
diff --git a/dpkg-deb/libtree.h b/dpkg-deb/libtree.h
new file mode 100644
index 0000000..cd47913
--- /dev/null
+++ b/dpkg-deb/libtree.h
@@ -0,0 +1,218 @@
+/*
+ * libtree.h - this file is part of Libtree.
+ *
+ * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; version 2 of the
+ * License.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+#ifndef _LIBTREE_H
+#define _LIBTREE_H
+
+#include <stdint.h>
+#include <stddef.h>
+
+/*
+ * The definition has been stolen from the Linux kernel.
+ */
+#ifdef __GNUC__
+#  define bstree_container_of(node, type, member) ({			\
+	const struct bstree_node *__mptr = (node);			\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+#  define rbtree_container_of(node, type, member) ({			\
+	const struct rbtree_node *__mptr = (node);			\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+#  define avltree_container_of(node, type, member) ({			\
+	const struct avltree_node *__mptr = (node);			\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+#  define splaytree_container_of(node, type, member) ({			\
+	const struct splaytree_node *__mptr = (node);			\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+#else
+#  define bstree_container_of(node, type, member)			\
+	((type *)((char *)(node) - offsetof(type, member)))
+#  define rbtree_container_of(node, type, member)			\
+	((type *)((char *)(node) - offsetof(type, member)))
+#  define avltree_container_of(node, type, member)			\
+	((type *)((char *)(node) - offsetof(type, member)))
+#  define splaytree_container_of(node, type, member)			\
+	((type *)((char *)(node) - offsetof(type, member)))
+#endif	/* __GNUC__ */
+
+/*
+ * Threaded binary search tree
+ */
+#ifdef UINTPTR_MAX
+
+struct bstree_node {
+	uintptr_t left, right;
+} __attribute__((aligned(2)));
+
+#else
+
+struct bstree_node {
+	struct bstree_node *left, *right;
+	unsigned left_is_thread:1;
+	unsigned right_is_thread:1;
+};
+
+#endif	/* UINTPTR_MAX */
+
+typedef int (*bstree_cmp_fn_t)(const struct bstree_node *, const struct bstree_node *);
+
+struct bstree {
+	struct bstree_node *root;
+	bstree_cmp_fn_t cmp_fn;
+	struct bstree_node *first, *last;
+	uint64_t reserved[4];
+};
+
+struct bstree_node *bstree_first(const struct bstree *tree);
+struct bstree_node *bstree_last(const struct bstree *tree);
+struct bstree_node *bstree_next(const struct bstree_node *node);
+struct bstree_node *bstree_prev(const struct bstree_node *node);
+
+struct bstree_node *bstree_lookup(const struct bstree_node *key, const struct bstree *tree);
+struct bstree_node *bstree_insert(struct bstree_node *node, struct bstree *tree);
+void bstree_remove(struct bstree_node *node, struct bstree *tree);
+void bstree_replace(struct bstree_node *old, struct bstree_node *node, struct bstree *tree);
+int bstree_init(struct bstree *tree, bstree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * Red-black tree
+ */
+enum rb_color {
+	RB_BLACK,
+	RB_RED,
+};
+
+#ifdef UINTPTR_MAX
+
+struct rbtree_node {
+	struct rbtree_node *left, *right;
+	uintptr_t parent;
+} __attribute__((aligned(2)));
+
+#else
+
+struct rbtree_node {
+	struct rbtree_node *left, *right;
+	struct rbtree_node *parent;
+	enum rb_color color;
+};
+
+#endif	/* UINTPTR_MAX */
+
+typedef int (*rbtree_cmp_fn_t)(const struct rbtree_node *, const struct rbtree_node *);
+
+struct rbtree {
+	struct rbtree_node *root;
+	rbtree_cmp_fn_t cmp_fn;
+	struct rbtree_node *first, *last;
+	uint64_t reserved[4];
+};
+
+struct rbtree_node *rbtree_first(const struct rbtree *tree);
+struct rbtree_node *rbtree_last(const struct rbtree *tree);
+struct rbtree_node *rbtree_next(const struct rbtree_node *node);
+struct rbtree_node *rbtree_prev(const struct rbtree_node *node);
+
+struct rbtree_node *rbtree_lookup(const struct rbtree_node *key, const struct rbtree *tree);
+struct rbtree_node *rbtree_insert(struct rbtree_node *node, struct rbtree *tree);
+void rbtree_remove(struct rbtree_node *node, struct rbtree *tree);
+void rbtree_replace(struct rbtree_node *old, struct rbtree_node *node, struct rbtree *tree);
+int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * AVL tree
+ */
+#if defined UINTPTR_MAX && UINTPTR_MAX == UINT64_MAX
+
+struct avltree_node {
+	struct avltree_node *left, *right;
+	uintptr_t parent;		/* balance factor [0:4] */
+} __attribute__((aligned(8)));
+
+#else
+
+struct avltree_node {
+	struct avltree_node *left, *right;
+	struct avltree_node *parent;
+	signed balance:3;		/* balance factor [-2:+2] */
+};
+
+#endif
+
+typedef int (*avltree_cmp_fn_t)(const struct avltree_node *, const struct avltree_node *);
+
+struct avltree {
+	struct avltree_node *root;
+	avltree_cmp_fn_t cmp_fn;
+	int height;
+	struct avltree_node *first, *last;
+	uint64_t reserved[4];
+};
+
+struct avltree_node *avltree_first(const struct avltree *tree);
+struct avltree_node *avltree_last(const struct avltree *tree);
+struct avltree_node *avltree_next(const struct avltree_node *node);
+struct avltree_node *avltree_prev(const struct avltree_node *node);
+
+struct avltree_node *avltree_lookup(const struct avltree_node *key, const struct avltree *tree);
+struct avltree_node *avltree_insert(struct avltree_node *node, struct avltree *tree);
+void avltree_remove(struct avltree_node *node, struct avltree *tree);
+void avltree_replace(struct avltree_node *old, struct avltree_node *node, struct avltree *tree);
+int avltree_init(struct avltree *tree, avltree_cmp_fn_t cmp, unsigned long flags);
+
+/*
+ * Splay tree
+ */
+#ifdef UINTPTR_MAX
+
+struct splaytree_node {
+	uintptr_t left, right;
+} __attribute__((aligned(2)));
+
+#else
+
+struct splaytree_node {
+	struct splaytree_node *left, *right;
+	unsigned left_is_thread:1;
+	unsigned right_is_thread:1;
+};
+
+#endif
+
+typedef int (*splaytree_cmp_fn_t)(const struct splaytree_node *, const struct splaytree_node *);
+
+struct splaytree {
+	struct splaytree_node *root;
+	struct splaytree_node *first, *last;
+	splaytree_cmp_fn_t cmp_fn;
+	uint64_t reserved[4];
+};
+
+struct splaytree_node *splaytree_first(const struct splaytree *tree);
+struct splaytree_node *splaytree_last(const struct splaytree *tree);
+struct splaytree_node *splaytree_next(const struct splaytree_node *node);
+struct splaytree_node *splaytree_prev(const struct splaytree_node *node);
+
+struct splaytree_node *splaytree_lookup(const struct splaytree_node *key, struct splaytree *tree);
+struct splaytree_node *splaytree_insert( struct splaytree_node *node, struct splaytree *tree);
+void splaytree_remove(struct splaytree_node *node, struct splaytree *tree);
+void splaytree_replace(struct splaytree_node *old, struct splaytree_node *node, struct splaytree *tree);
+int splaytree_init(struct splaytree *tree, splaytree_cmp_fn_t cmp, unsigned long flags);
+
+#endif /* _LIBTREE_H */
diff --git a/dpkg-deb/rb.c b/dpkg-deb/rb.c
new file mode 100644
index 0000000..f2fc365
--- /dev/null
+++ b/dpkg-deb/rb.c
@@ -0,0 +1,485 @@
+/*
+ * rbtree - Implements a red-black tree with parent pointers.
+ *
+ * Copyright (C) 2010 Franck Bui-Huu <fbuihuu@gmail.com>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation; version 2 of the
+ * License.
+ *
+ * This library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+
+/*
+ * For recall a red-black tree has the following properties:
+ *
+ *     1. All nodes are either BLACK or RED
+ *     2. Leafs are BLACK
+ *     3. A RED node has BLACK children only
+ *     4. Path from a node to any leafs has the same number of BLACK nodes.
+ *
+ */
+#include "libtree.h"
+
+/*
+ * Some helpers
+ */
+#ifdef UINTPTR_MAX
+
+static inline enum rb_color get_color(const struct rbtree_node *node)
+{
+	return node->parent & 1;
+}
+
+static inline void set_color(enum rb_color color, struct rbtree_node *node)
+{
+	node->parent = (node->parent & ~1UL) | color;
+}
+
+static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
+{
+	return (struct rbtree_node *)(node->parent & ~1UL);
+}
+
+static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
+{
+	node->parent = (uintptr_t)parent | (node->parent & 1);
+}
+
+#else
+
+static inline enum rb_color get_color(const struct rbtree_node *node)
+{
+	return node->color;
+}
+
+static inline void set_color(enum rb_color color, struct rbtree_node *node)
+{
+	node->color = color;
+}
+
+static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
+{
+	return node->parent;
+}
+
+static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
+{
+	node->parent = parent;
+}
+
+#endif	/* UINTPTR_MAX */
+
+static inline int is_root(struct rbtree_node *node)
+{
+	return get_parent(node) == NULL;
+}
+
+static inline int is_black(struct rbtree_node *node)
+{
+	return get_color(node) == RB_BLACK;
+}
+
+static inline int is_red(struct rbtree_node *node)
+{
+	return !is_black(node);
+}
+
+/*
+ * Iterators
+ */
+static inline struct rbtree_node *get_first(struct rbtree_node *node)
+{
+	while (node->left)
+		node = node->left;
+	return node;
+}
+
+static inline struct rbtree_node *get_last(struct rbtree_node *node)
+{
+	while (node->right)
+		node = node->right;
+	return node;
+}
+
+struct rbtree_node *rbtree_first(const struct rbtree *tree)
+{
+	return tree->first;
+}
+
+struct rbtree_node *rbtree_last(const struct rbtree *tree)
+{
+	return tree->last;
+}
+
+struct rbtree_node *rbtree_next(const struct rbtree_node *node)
+{
+	struct rbtree_node *parent;
+
+	if (node->right)
+		return get_first(node->right);
+
+	while ((parent = get_parent(node)) && parent->right == node)
+		node = parent;
+	return parent;
+}
+
+struct rbtree_node *rbtree_prev(const struct rbtree_node *node)
+{
+	struct rbtree_node *parent;
+
+	if (node->left)
+		return get_last(node->left);
+
+	while ((parent = get_parent(node)) && parent->left == node)
+		node = parent;
+	return parent;
+}
+
+/*
+ * 'pparent' and 'is_left' are only used for insertions. Normally GCC
+ * will notice this and get rid of them for lookups.
+ */
+static inline struct rbtree_node *do_lookup(const struct rbtree_node *key,
+					    const struct rbtree *tree,
+					    struct rbtree_node **pparent,
+					    int *is_left)
+{
+	struct rbtree_node *node = tree->root;
+
+	*pparent = NULL;
+	*is_left = 0;
+
+	while (node) {
+		int res = tree->cmp_fn(node, key);
+		if (res == 0)
+			return node;
+		*pparent = node;
+		if ((*is_left = res > 0))
+			node = node->left;
+		else
+			node = node->right;
+	}
+	return NULL;
+}
+
+/*
+ * Rotate operations (They preserve the binary search tree property,
+ * assuming that the keys are unique).
+ */
+static void rotate_left(struct rbtree_node *node, struct rbtree *tree)
+{
+	struct rbtree_node *p = node;
+	struct rbtree_node *q = node->right; /* can't be NULL */
+	struct rbtree_node *parent = get_parent(p);
+
+	if (!is_root(p)) {
+		if (parent->left == p)
+			parent->left = q;
+		else
+			parent->right = q;
+	} else
+		tree->root = q;
+	set_parent(parent, q);
+	set_parent(q, p);
+
+	p->right = q->left;
+	if (p->right)
+		set_parent(p, p->right);
+	q->left = p;
+}
+
+static void rotate_right(struct rbtree_node *node, struct rbtree *tree)
+{
+	struct rbtree_node *p = node;
+	struct rbtree_node *q = node->left; /* can't be NULL */
+	struct rbtree_node *parent = get_parent(p);
+
+	if (!is_root(p)) {
+		if (parent->left == p)
+			parent->left = q;
+		else
+			parent->right = q;
+	} else
+		tree->root = q;
+	set_parent(parent, q);
+	set_parent(q, p);
+
+	p->left = q->right;
+	if (p->left)
+		set_parent(p, p->left);
+	q->right = p;
+}
+
+struct rbtree_node *rbtree_lookup(const struct rbtree_node *key,
+				  const struct rbtree *tree)
+{
+	struct rbtree_node *parent;
+	int is_left;
+
+	return do_lookup(key, tree, &parent, &is_left);
+}
+
+static void set_child(struct rbtree_node *child, struct rbtree_node *node, int left)
+{
+	if (left)
+		node->left = child;
+	else
+		node->right = child;
+}
+
+struct rbtree_node *rbtree_insert(struct rbtree_node *node, struct rbtree *tree)
+{
+	struct rbtree_node *key, *parent;
+	int is_left;
+
+	key = do_lookup(node, tree, &parent, &is_left);
+	if (key)
+		return key;
+
+	node->left = NULL;
+	node->right = NULL;
+	set_color(RB_RED, node);
+	set_parent(parent, node);
+
+	if (parent) {
+		if (is_left) {
+			if (parent == tree->first)
+				tree->first = node;
+		} else {
+			if (parent == tree->last)
+				tree->last = node;
+		}
+		set_child(node, parent, is_left);
+	} else {
+		tree->root = node;
+		tree->first = node;
+		tree->last = node;
+	}
+
+	/*
+	 * Fixup the modified tree by recoloring nodes and performing
+	 * rotations (2 at most) hence the red-black tree properties are
+	 * preserved.
+	 */
+	while ((parent = get_parent(node)) && is_red(parent)) {
+		struct rbtree_node *grandpa = get_parent(parent);
+
+		if (parent == grandpa->left) {
+			struct rbtree_node *uncle = grandpa->right;
+
+			if (uncle && is_red(uncle)) {
+				set_color(RB_BLACK, parent);
+				set_color(RB_BLACK, uncle);
+				set_color(RB_RED, grandpa);
+				node = grandpa;
+			} else {
+				if (node == parent->right) {
+					rotate_left(parent, tree);
+					node = parent;
+					parent = get_parent(node);
+				}
+				set_color(RB_BLACK, parent);
+				set_color(RB_RED, grandpa);
+				rotate_right(grandpa, tree);
+			}
+		} else {
+			struct rbtree_node *uncle = grandpa->left;
+
+			if (uncle && is_red(uncle)) {
+				set_color(RB_BLACK, parent);
+				set_color(RB_BLACK, uncle);
+				set_color(RB_RED, grandpa);
+				node = grandpa;
+			} else {
+				if (node == parent->left) {
+					rotate_right(parent, tree);
+					node = parent;
+					parent = get_parent(node);
+				}
+				set_color(RB_BLACK, parent);
+				set_color(RB_RED, grandpa);
+				rotate_left(grandpa, tree);
+			}
+		}
+	}
+	set_color(RB_BLACK, tree->root);
+	return NULL;
+}
+
+void rbtree_remove(struct rbtree_node *node, struct rbtree *tree)
+{
+	struct rbtree_node *parent = get_parent(node);
+	struct rbtree_node *left = node->left;
+	struct rbtree_node *right = node->right;
+	struct rbtree_node *next;
+	enum rb_color color;
+
+	if (node == tree->first)
+		tree->first = rbtree_next(node);
+	if (node == tree->last)
+		tree->last = rbtree_prev(node);
+
+	if (!left)
+		next = right;
+	else if (!right)
+		next = left;
+	else
+		next = get_first(right);
+
+	if (parent)
+		set_child(next, parent, parent->left == node);
+	else
+		tree->root = next;
+
+	if (left && right) {
+		color = get_color(next);
+		set_color(get_color(node), next);
+
+		next->left = left;
+		set_parent(next, left);
+
+		if (next != right) {
+			parent = get_parent(next);
+			set_parent(get_parent(node), next);
+
+			node = next->right;
+			parent->left = node;
+
+			next->right = right;
+			set_parent(next, right);
+		} else {
+			set_parent(parent, next);
+			parent = next;
+			node = next->right;
+		}
+	} else {
+		color = get_color(node);
+		node = next;
+	}
+	/*
+	 * 'node' is now the sole successor's child and 'parent' its
+	 * new parent (since the successor can have been moved).
+	 */
+	if (node)
+		set_parent(parent, node);
+
+	/*
+	 * The 'easy' cases.
+	 */
+	if (color == RB_RED)
+		return;
+	if (node && is_red(node)) {
+		set_color(RB_BLACK, node);
+		return;
+	}
+
+	do {
+		if (node == tree->root)
+			break;
+
+		if (node == parent->left) {
+			struct rbtree_node *sibling = parent->right;
+
+			if (is_red(sibling)) {
+				set_color(RB_BLACK, sibling);
+				set_color(RB_RED, parent);
+				rotate_left(parent, tree);
+				sibling = parent->right;
+			}
+			if ((!sibling->left  || is_black(sibling->left)) &&
+			    (!sibling->right || is_black(sibling->right))) {
+				set_color(RB_RED, sibling);
+				node = parent;
+				parent = get_parent(parent);
+				continue;
+			}
+			if (!sibling->right || is_black(sibling->right)) {
+				set_color(RB_BLACK, sibling->left);
+				set_color(RB_RED, sibling);
+				rotate_right(sibling, tree);
+				sibling = parent->right;
+			}
+			set_color(get_color(parent), sibling);
+			set_color(RB_BLACK, parent);
+			set_color(RB_BLACK, sibling->right);
+			rotate_left(parent, tree);
+			node = tree->root;
+			break;
+		} else {
+			struct rbtree_node *sibling = parent->left;
+
+			if (is_red(sibling)) {
+				set_color(RB_BLACK, sibling);
+				set_color(RB_RED, parent);
+				rotate_right(parent, tree);
+				sibling = parent->left;
+			}
+			if ((!sibling->left  || is_black(sibling->left)) &&
+			    (!sibling->right || is_black(sibling->right))) {
+				set_color(RB_RED, sibling);
+				node = parent;
+				parent = get_parent(parent);
+				continue;
+			}
+			if (!sibling->left || is_black(sibling->left)) {
+				set_color(RB_BLACK, sibling->right);
+				set_color(RB_RED, sibling);
+				rotate_left(sibling, tree);
+				sibling = parent->left;
+			}
+			set_color(get_color(parent), sibling);
+			set_color(RB_BLACK, parent);
+			set_color(RB_BLACK, sibling->left);
+			rotate_right(parent, tree);
+			node = tree->root;
+			break;
+		}
+	} while (is_black(node));
+
+	if (node)
+		set_color(RB_BLACK, node);
+}
+
+void rbtree_replace(struct rbtree_node *old, struct rbtree_node *new,
+		    struct rbtree *tree)
+{
+	struct rbtree_node *parent = get_parent(old);
+
+	if (parent)
+		set_child(new, parent, parent->left == old);
+	else
+		tree->root = new;
+
+	if (old->left)
+		set_parent(new, old->left);
+	if (old->right)
+		set_parent(new, old->right);
+
+	if (tree->first == old)
+		tree->first = new;
+	if (tree->last == old)
+		tree->last = new;
+
+	*new = *old;
+}
+
+int rbtree_init(struct rbtree *tree, rbtree_cmp_fn_t fn, unsigned long flags)
+{
+	if (flags)
+		return -1;
+	tree->root = NULL;
+	tree->cmp_fn = fn;
+	tree->first = NULL;
+	tree->last = NULL;
+	return 0;
+}
-- 
1.8.4.rc3

Message #29 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Guillem Jover <guillem@debian.org>

To: Shawn Landden <shawnlandden@gmail.com>

Cc: debian-dpkg@lists.debian.org, 719845@bugs.debian.org

Subject: Re: [PATCH] convert file_info from singlely-linked list to rbtree

Date: Fri, 23 Aug 2013 00:59:56 +0200

Hi!

On Thu, 2013-08-22 at 12:16:33 -0700, Shawn Landden wrote:
> now filenames are sorted via tree-sort to increase determinism in builds
> 
> lookup (was only used in check_conffiles()) is now O(log(n)) instead
> of O(n)

The problem is that this makes the build stall on sorting, because it
has to slurp all input from the pipe before it can start feeding paths
to tar. It also consumes lots more memory, as it needs to keep all
that data before it can start writing it out. It's the equivalent of
injecting a "sort" into the "find" pipe, which would have been the
easier solution, and the reason I've not done just that before.

In any case today I finished a directory tree walker I started writing
yesterday, that I was going to need anyway to add tar write support,
which sorts per directory, so that the stalls are pretty small, and
frees stuff as it goes taking a similar amount of memory as the
unsorted find command. I need to clean it up a bit, and prepare some
tests but I'll merge that for 1.17.2 or 1.17.3.

> The license of libtree is a bit funny: _Library_ GPL _2_ (which doesn't exist)
> I have asked upstream for clarification on this:
> 
> https://github.com/fbuihuu/libtree/issues/7

Well that'd be <http://www.gnu.org/licenses/old-licenses/lgpl-2.0.html>.

I've been trying to get rid of GPLv2-only code, so I'm not planning
on merging any new code with such license anyway.

Thanks,
Guillem

Message #34 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Shawn <shawnlandden@gmail.com>

To: Shawn Landden <shawnlandden@gmail.com>, debian-dpkg@lists.debian.org, 719845@bugs.debian.org

Subject: Re: [PATCH] convert file_info from singlely-linked list to rbtree

Date: Thu, 22 Aug 2013 16:06:45 -0700

[Message part 1 (text/plain, inline)]

On Thu, Aug 22, 2013 at 3:59 PM, Guillem Jover <guillem@debian.org> wrote:

> > The license of libtree is a bit funny: _Library_ GPL _2_ (which doesn't
> exist)
> > I have asked upstream for clarification on this:
> >
> > https://github.com/fbuihuu/libtree/issues/7
>
> Well that'd be <http://www.gnu.org/licenses/old-licenses/lgpl-2.0.html>.
>
> I've been trying to get rid of GPLv2-only code, so I'm not planning
> on merging any new code with such license anyway.
>
whoops, i got confused in my head, the source reads "Lesser General Public
License 2", which is the one that doesn't exist.
-- 

---
Shawn Landden
+1 360 389 3001 (SMS preferred)

[Message part 2 (text/html, inline)]

Message #39 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: [PATCH] t-deterministic-file-order: new test case

Date: Tue, 27 Aug 2013 23:12:34 +0200

[Message part 1 (text/plain, inline)]

In order to make the build reproducible, we ensure that the files are
written to the .deb in a deterministic file order.
---

Here is a test case for pkg-tests that should ensure that files are
always written in the same order in the control and data tarball,
despite what readdir() says.

 t-deterministic-file-order/Makefile                |   28 +++++
 t-deterministic-file-order/hookdir.c               |  110 ++++++++++++++++++++
 .../pkg-file-order/DEBIAN/control                  |    7 ++
 .../pkg-file-order/DEBIAN/md5sums                  |    2 +
 4 files changed, 147 insertions(+)
 create mode 100644 t-deterministic-file-order/Makefile
 create mode 100644 t-deterministic-file-order/hookdir.c
 create mode 100644 t-deterministic-file-order/pkg-file-order/DEBIAN/control
 create mode 100644 t-deterministic-file-order/pkg-file-order/DEBIAN/md5sums
 create mode 100644 t-deterministic-file-order/pkg-file-order/a
 create mode 100644 t-deterministic-file-order/pkg-file-order/b

diff --git a/t-deterministic-file-order/Makefile b/t-deterministic-file-order/Makefile
new file mode 100644
index 0000000..5ba11b0
--- /dev/null
+++ b/t-deterministic-file-order/Makefile
@@ -0,0 +1,28 @@
+include ../Test.mk
+
+test-case: libhookdir.so
+	rm -rf pkg-file-order-1 && cp -a pkg-file-order pkg-file-order-1
+	rm -rf pkg-file-order-2 && cp -a pkg-file-order pkg-file-order-2
+
+	$(DPKG_BUILD_DEB) pkg-file-order-1
+	LD_PRELOAD=$$(pwd)/libhookdir.so $(DPKG_BUILD_DEB) pkg-file-order-2
+
+	ar x pkg-file-order-1.deb
+	tar -ztf control.tar.gz > content-control-1
+	tar -atf data.tar.* > content-data-1
+	ar x pkg-file-order-2.deb
+	tar -ztf control.tar.gz > content-control-2
+	tar -atf data.tar.* > content-data-2
+	diff -u content-control-1 content-control-2
+	diff -u content-data-1 content-data-2
+
+test-clean:
+	rm -rf pkg-file-order-1 pkg-file-order-2
+	rm -f pkg-file-order-1.deb pkg-file-order-2.deb
+	rm -f data.tar.* control.tar.* debian-binary
+	rm -f content-control-1 content-control-2
+	rm -f content-data-1 content-data-2
+	rm -f libhookdir.so
+
+libhookdir.so: hookdir.c
+	gcc -Wall -shared -fPIC -o $@ $< -ldl
diff --git a/t-deterministic-file-order/hookdir.c b/t-deterministic-file-order/hookdir.c
new file mode 100644
index 0000000..49c4bd1
--- /dev/null
+++ b/t-deterministic-file-order/hookdir.c
@@ -0,0 +1,110 @@
+/* libhookdir.c: LD_PRELOAD lib to return readdir() results in reverse order
+ * Code snippet from Niklas B. copied from <http://stackoverflow.com/a/8866709>
+ * Licensed under CC BY-SA 3.0
+ */
+
+#define _GNU_SOURCE 1
+#include <stdio.h>
+#include <dirent.h>
+#include <dlfcn.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct __dirstream
+{
+  int __fd;
+  char *__data;
+  size_t __allocation;
+  size_t __offset;
+  size_t __size;
+  struct dirent __entry;
+};
+
+typedef struct _dirent_list {
+  struct dirent *value;
+  struct _dirent_list *next;
+} dirent_list;
+
+typedef struct _my_DIR {
+  struct __dirstream orig;
+  dirent_list *first_entry;
+  int first_readdir;
+} my_DIR;
+
+DIR *fdopendir(int fd) {
+  DIR *(*orig_fdopendir)(int) = dlsym(RTLD_NEXT, "fdopendir");
+  DIR *dir = orig_fdopendir(fd);
+
+  // save additional information along with the
+  // original DIR structure
+  my_DIR *my_dir = calloc(1, sizeof(*my_dir));
+  my_dir->first_readdir = 1;
+  memcpy(my_dir, dir, sizeof(*dir));
+  return (DIR*)my_dir;
+}
+
+DIR *opendir(const char *name) {
+  DIR *(*orig_opendir)(const char*) = dlsym(RTLD_NEXT, "opendir");
+  DIR *dir = orig_opendir(name);
+
+  // save additional information along with the
+  // original DIR structure
+  my_DIR *my_dir = calloc(1, sizeof(*my_dir));
+  my_dir->first_readdir = 1;
+  memcpy(my_dir, dir, sizeof(*dir));
+  return (DIR*)my_dir;
+}
+
+struct dirent *readdir(DIR *dir) {
+  struct dirent *(*orig_readdir)(DIR*) = dlsym(RTLD_NEXT, "readdir");
+  my_DIR *my_dir = (my_DIR*)dir;
+  dirent_list *item;
+
+  if (my_dir->first_readdir) {
+    struct dirent *entry;
+    while ((entry = orig_readdir(dir))) {
+      item = calloc(1, sizeof(*item));
+      item->value = entry;
+      item->next = my_dir->first_entry;
+      my_dir->first_entry = item;
+    }
+    my_dir->first_readdir = 0;
+  }
+
+  if (!my_dir->first_entry)
+    return NULL;
+
+  item = my_dir->first_entry;
+  struct dirent *result = item->value;
+  my_dir->first_entry = item->next;
+  free(item);
+
+  return result;
+}
+
+int closedir(DIR *dir) {
+  int (*orig_closedir)(DIR *) = dlsym(RTLD_NEXT, "closedir");
+
+  return orig_closedir(dir);
+}
+
+long telldir(DIR *dir) {
+  long (*orig_telldir)(DIR *) = dlsym(RTLD_NEXT, "telldir");
+
+  fprintf(stderr, "telldir(%p): not properly implemented in libhookdir\n", dir);
+  return orig_telldir(dir);
+}
+
+void seekdir(DIR *dir, long offset) {
+  void (*orig_seekdir)(DIR *, long) = dlsym(RTLD_NEXT, "seekdir");
+
+  fprintf(stderr, "seekdir(%p, %ld): not properly implemented in libhookdir\n", dir, offset);
+  return orig_seekdir(dir, offset);
+}
+
+void rewinddir(DIR *dir) {
+  void (*orig_rewinddir)(DIR *) = dlsym(RTLD_NEXT, "rewinddir");
+
+  fprintf(stderr, "rewinddir(%p): not properly implemented in libhookdir\n", dir);
+  return orig_rewinddir(dir);
+}
diff --git a/t-deterministic-file-order/pkg-file-order/DEBIAN/control b/t-deterministic-file-order/pkg-file-order/DEBIAN/control
new file mode 100644
index 0000000..a7f4437
--- /dev/null
+++ b/t-deterministic-file-order/pkg-file-order/DEBIAN/control
@@ -0,0 +1,7 @@
+Package: pkg-file-order
+Version: 0.0-1
+Section: test
+Priority: extra
+Maintainer: Dpkg Developers <debian-dpkg@lists.debian.org>
+Architecture: all
+Description: test package for deterministic file ordering
diff --git a/t-deterministic-file-order/pkg-file-order/DEBIAN/md5sums b/t-deterministic-file-order/pkg-file-order/DEBIAN/md5sums
new file mode 100644
index 0000000..70ef2fa
--- /dev/null
+++ b/t-deterministic-file-order/pkg-file-order/DEBIAN/md5sums
@@ -0,0 +1,2 @@
+d41d8cd98f00b204e9800998ecf8427e  a
+d41d8cd98f00b204e9800998ecf8427e  b
diff --git a/t-deterministic-file-order/pkg-file-order/a b/t-deterministic-file-order/pkg-file-order/a
new file mode 100644
index 0000000..e69de29
diff --git a/t-deterministic-file-order/pkg-file-order/b b/t-deterministic-file-order/pkg-file-order/b
new file mode 100644
index 0000000..e69de29
-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[signature.asc (application/pgp-signature, inline)]

Message #44 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Guillem Jover <guillem@debian.org>

To: Jérémy Bobbio <lunar@debian.org>, 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] t-deterministic-file-order: new test case

Date: Wed, 28 Aug 2013 04:50:33 +0200

Hi!

On Tue, 2013-08-27 at 23:12:34 +0200, Jérémy Bobbio wrote:
> In order to make the build reproducible, we ensure that the files are
> written to the .deb in a deterministic file order.
> ---
> 
> Here is a test case for pkg-tests that should ensure that files are
> always written in the same order in the control and data tarball,
> despite what readdir() says.

Thanks, this is very helpful. I've applied it locally, and done
several simplifications. I've removed the libhookdir library, because
it's really unneeded and it makes unportable assumptions on the internal
structure of the DIR type (which in this case seems to be missing an
off_t member). I'm just checking the .deb member tar output against a
sorted tar output. I've also renamed the test case.

Thanks,
Guillem

Message #49 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] t-deterministic-file-order: new test case

Date: Wed, 28 Aug 2013 07:59:18 +0200

[Message part 1 (text/plain, inline)]

Guillem Jover:
> On Tue, 2013-08-27 at 23:12:34 +0200, Jérémy Bobbio wrote:
> > In order to make the build reproducible, we ensure that the files are
> > written to the .deb in a deterministic file order.
> > ---
> > 
> > Here is a test case for pkg-tests that should ensure that files are
> > always written in the same order in the control and data tarball,
> > despite what readdir() says.
> 
> Thanks, this is very helpful. I've applied it locally, and done
> several simplifications. I've removed the libhookdir library, because
> it's really unneeded and it makes unportable assumptions on the internal
> structure of the DIR type (which in this case seems to be missing an
> off_t member). I'm just checking the .deb member tar output against a
> sorted tar output.

How do you ensure that readdir() will not return files in sorted
order?

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[signature.asc (application/pgp-signature, inline)]

Message #54 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Cc: reproducible-builds@lists.alioth.debian.org

Subject: [PATCH] Deterministic file order for control and data archives

Date: Fri, 17 Jan 2014 20:33:37 +0100

[Message part 1 (text/plain, inline)]

Control: tags -1 + patch

Hi!

Here are four patches based on the current master (1e059955) that will
write files in deterministic order in the control and data archives.
File names are sorted by forking `sort` before being piped to `tar`.

They have been tested with the test case previously sent and on bigger
packages.

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[0001-Ensure-deterministic-file-order-in-data.tar.-files.patch (text/x-diff, attachment)]

[0002-Extract-the-creation-of-the-control-tarball-to-a-ded.patch (text/x-diff, attachment)]

[0003-Rename-create_control_tar-variables-to-more-meaningf.patch (text/x-diff, attachment)]

[0004-Also-write-control.tar.gz-in-deterministic-order.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #61 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] Deterministic file order for control and data archives

Date: Fri, 29 Aug 2014 01:04:39 +0000

[Message part 1 (text/plain, inline)]

Hi!

Jérémy Bobbio:
> Here are four patches based on the current master (1e059955) that will
> write files in deterministic order in the control and data archives.
> File names are sorted by forking `sort` before being piped to `tar`.

Attached are the same patches rebased on the current master (29422bfd).

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[0001-Ensure-deterministic-file-order-in-data.tar.-files.patch (text/x-diff, attachment)]

[0002-Extract-the-creation-of-the-control-tarball-to-a-ded.patch (text/x-diff, attachment)]

[0003-Rename-create_control_tar-variables-to-more-meaningf.patch (text/x-diff, attachment)]

[0004-Also-write-control.tar.gz-in-deterministic-order.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #66 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] Deterministic file order for control and data archives

Date: Mon, 6 Oct 2014 10:19:46 +0200

[Message part 1 (text/plain, inline)]

Jérémy Bobbio:
> Here are four patches based on the current master (1e059955) that will
> write files in deterministic order in the control and data archives.
> File names are sorted by forking `sort` before being piped to `tar`.

Attached are the patch based on current master (36eda4c1bc).

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[0001-Ensure-deterministic-file-order-in-data.tar.-files.patch (text/x-diff, attachment)]

[0002-Extract-the-creation-of-the-control-tarball-to-a-ded.patch (text/x-diff, attachment)]

[0003-Rename-create_control_tar-variables-to-more-meaningf.patch (text/x-diff, attachment)]

[0004-Also-write-control.tar.gz-in-deterministic-order.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #71 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Phil Miller <unmobile@gmail.com>

To: 719845@bugs.debian.org

Subject: Bug#719845: Will be easier to fix after patching findutils

Date: Mon, 29 Dec 2014 17:53:02 -0600

[Message part 1 (text/plain, inline)]

I've just submitted a patch to GNU findutils that adds a -sort option doing
the obvious thing. As noted in the earlier comments, this would be
preferable to piping to sort. It's also a much smaller change than adding
that into the pipeline.

Hopefully, that will have reached upstream and been packaged before this
issue gets revisited.

[Message part 2 (text/html, inline)]

Message #76 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] Deterministic file order for control and data archives

Date: Thu, 25 Jun 2015 00:22:19 +0200

[Message part 1 (text/plain, inline)]

Jérémy Bobbio:
> Jérémy Bobbio:
> > Here are four patches based on the current master (1e059955) that will
> > write files in deterministic order in the control and data archives.
> > File names are sorted by forking `sort` before being piped to `tar`.
> 
> Attached are the patch based on current master (36eda4c1bc).

Attached are the patch based on master (1b8c20ad2).

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[0001-Ensure-deterministic-file-order-in-data.tar.-files.patch (text/x-diff, attachment)]

[0002-Extract-the-creation-of-the-control-tarball-to-a-ded.patch (text/x-diff, attachment)]

[0003-Rename-create_control_tar-variables-to-more-meaningf.patch (text/x-diff, attachment)]

[0004-Also-write-control.tar.gz-in-deterministic-order.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #81 received at 719845@bugs.debian.org (full text, mbox, reply):

From: Jérémy Bobbio <lunar@debian.org>

To: 719845@bugs.debian.org

Subject: Re: Bug#719845: [PATCH] Deterministic file order for control and data archives

Date: Thu, 8 Oct 2015 16:39:21 +0200

[Message part 1 (text/plain, inline)]

Jérémy Bobbio:
> Jérémy Bobbio:
> > Jérémy Bobbio:
> > > Here are four patches based on the current master (1e059955) that will
> > > write files in deterministic order in the control and data archives.
> > > File names are sorted by forking `sort` before being piped to `tar`.
> > 
> > Attached are the patch based on current master (36eda4c1bc).
> 
> Attached are the patch based on master (1b8c20ad2).

Attached is a much simpler replacement for the earlier 3 patches:
> Subject: [PATCH 2/4] Extract the creation of the control tarball to a
> Subject: [PATCH 3/4] Rename create_control_tar() variables to more meaningful
> Subject: [PATCH 4/4] Also write control.tar.gz in deterministic order

Instead of feeding the list of control files using `find+sort`, we now
use the new `--sort=name` option that has been added in GNU Tar 1.28.
This makes making the order of control.tar deterministic a simple
one-line change.

tar/1.28-1 is already in testing. I think it's fine to ask a more recent
tar to be used when building packages with a more recent version of
dpkg-dev.

-- 
Lunar                                .''`. 
lunar@debian.org                    : :Ⓐ  :  # apt-get install anarchism
                                    `. `'` 
                                      `-   

[0001-Write-control.tar-in-a-deterministic-order.patch (text/x-diff, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #84 received at 719845-submitter@bugs.debian.org (full text, mbox, reply):

From: Guillem Jover <guillem@debian.org>

To: 719845-submitter@bugs.debian.org

Subject: Bug#719845 in package dpkg marked as pending

Date: Sat, 27 Feb 2016 00:48:05 +0000

Control: tag 719845 pending

Hi!

Bug #719845 in package dpkg reported by you has been fixed in
the dpkg/dpkg.git Git repository. You can see the changelog below, and
you can check the diff of the fix at:

    https://anonscm.debian.org/cgit/dpkg/dpkg.git/diff/?id=513a6a9

---
commit 513a6a9b568d3d65cc19f3caa72ce32a0af391a2
Author: Guillem Jover <guillem@debian.org>
Date:   Fri Feb 26 10:51:57 2016 +0100

    dpkg-deb: Use the treewalk module to build the .deb control member
    
    We reduce external dependencies on commands, and get sorted file lists.
    
    Closes: #719845

diff --git a/debian/changelog b/debian/changelog
index a684a14..a6d4c91 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -39,6 +39,8 @@ dpkg (1.18.5) UNRELEASED; urgency=medium
     duplicate stat(2) calls, not calling find(1), and sorting the output w/o
     stalling on the entire input being slurped and sorted.
     - Use it to build the .deb data member in dpkg-deb.
+    - Use it to build the .deb control member in dpkg-deb.
+    Closes: #719845
   * Portability:
     - Move DPKG_ADMINDIR environment variable name out from update-alternatives
       code, to make life easier for non-dpkg-based systems.

Message #91 received at 719845-close@bugs.debian.org (full text, mbox, reply):

From: Guillem Jover <guillem@debian.org>

To: 719845-close@bugs.debian.org

Subject: Bug#719845: fixed in dpkg 1.18.5

Date: Mon, 02 May 2016 04:19:41 +0000

Source: dpkg
Source-Version: 1.18.5

We believe that the bug you reported is fixed in the latest version of
dpkg, which is due to be installed in the Debian FTP archive.

A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 719845@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Guillem Jover <guillem@debian.org> (supplier of updated dpkg package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@ftp-master.debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Format: 1.8
Date: Mon, 02 May 2016 04:14:57 +0200
Source: dpkg
Binary: libdpkg-dev dpkg dpkg-dev libdpkg-perl dselect
Architecture: source
Version: 1.18.5
Distribution: unstable
Urgency: medium
Maintainer: Dpkg Developers <debian-dpkg@lists.debian.org>
Changed-By: Guillem Jover <guillem@debian.org>
Description:
 dpkg       - Debian package management system
 dpkg-dev   - Debian package development tools
 dselect    - Debian package management front-end
 libdpkg-dev - Debian package management static library
 libdpkg-perl - Dpkg perl modules
Closes: 719845 780906 784806 784808 795163 804624 807340 809174 809219 809517 809963 810720 811037 811267 812679 813179 819194 819939 819940 821025 822797 822798
Changes:
 dpkg (1.18.5) unstable; urgency=medium
 .
   [ Guillem Jover ]
   * Print correct integer parse error for short-only command-line options.
     This affects «dpkg-deb -z». Closes: #809174
   * Do not abort when traversing symlinks to directories in dpkg-scanpackages
     and dpkg-scansources. Closes: #809219
   * Implement delete operator with size argument in dselect, required by the
     C++14 spec when the size-less delete operator is defined.
   * Use EACCES instead of EWOULDBLOCK for fcntl(2) F_SETLK in dselect.
   * Print the archive filename when dpkg cannot access it.
   * Check that all passed archive filenames to dpkg exist before queuing them.
     Closes: #809963
   * Use ohshit() instead of internerr() for unhandled dpkg-split exit codes.
     (i.e. do not abort). Closes: #812679
   * Detect non-regular file archive arguments earlier in dpkg.
   * Switch URLs in docs, code comments and packaging, from http:// or git://
     to https:// if the latter is available (round three). This includes the
     dpkg git repository, copyright format URL and examples in man pages among
     others.
   * Clarify where to find the GPL-2 license in debian/copyright.
   * Do not enable stack-protector on nios2 in Debian and derivatives (it is
     not supported by gcc yet).
   * Check first for build type to short-circuit boolean expressions in
     dpkg-genchanges.
   * Add source format backend-specific --help options support to dpkg-source.
   * Add MIPS R6 architectures to arch tables. Closes: #807340
     Thanks to YunQiang Su <wzssyqa@gmail.com>.
   * Fix memory leak when unpacking conffiles.
   * Use fixed string matching for pathnames in dpkg-maintscript-helper.
     Thanks to Carsten Hey <carsten@debian.org>.
   * Quote shell variables in dpkg-maintscript-helper.
     Thanks to Carsten Hey <carsten@debian.org>.
   * Anchor pathnames in sed and grep regexes in dpkg-maintscript-helper.
     Thanks to Carsten Hey <carsten@debian.org>.
   * Allow broken versions starting with a dash in dpkg-maintscript-helper.
     Thanks to Carsten Hey <carsten@debian.org>.
   * Add a new treewalk module in libdpkg, with the nice properties of avoiding
     duplicate stat(2) calls, not calling find(1), and sorting the output w/o
     stalling on the entire input being slurped and sorted.
     - Use it to build the .deb data member in dpkg-deb.
     - Use it to build the .deb control member in dpkg-deb.
     Closes: #719845
     - Use it with dpkg --recursive option.
   * Unify start-stop-daemon --help output with the rest of the tools.
   * Search for debsig-verify in PATH instead of using an absolute path.
   * Do not error out when failing to open the SE label db on permissive mode.
     Closes: #811037
   * Rewrite the trigger deferred file parser from flex to manual. The format
     is very simple, and a simple hand-written parser is smaller and avoids a
     build dependency.
   * Be more strict when parsing the COLUMNS environment variable in dpkg-query.
   * Make the Architecture field mandatory on package builds.
   * Use new Dpkg::Arch functions to validate and parse architectures when
     building source packages. Closes: #784808
   * Do safe matching of directories containing conffiles in
     dpkg-maintscript-helper, instead of using a variable pathname as a regex
     with grep, which is susceptible to metacharacters acting as part of the
     regex. Proposed by Carsten Hey <carsten@debian.org>.
   * Decouple local keyword declaration from command assignment in
     dpkg-maintscript-helper, which masks the command return value when
     using «set -e».
   * Make dpkg pass <new-version> to maintscript actions that cannot get it
     otherwise. These actions are now:
     - <new-postrm> failed-upgrade <old-version> <new-version>
     - <new-postrm> abort-install <old-version> <new-version>
     - <new-postrm> abort-upgrade <old-version> <new-version>
     - <new-preinst> install <old-version> <new-version>
     - <new-preinst> upgrade <old-version> <new-version>
     - <new-prerm> failed-upgrade <old-version> <new-version>
     Prompted by Andrey Utkin <andrey.krieger.utkin@gmail.com>.
   * Promote a print to a warning for missing control files in dpkg-deb.
   * Use info() instead of print in dpkg-buildpackage and dpkg-genchanges.
   * Add very basic color support to all dpkg namespaced programs, enabled by
     setting the environment variable DPKG_COLORS to “auto”, “always” or
     “never”, the latter being the default.
   * Add support for a new --build option to define build type by a
     comma-separated list of components (“source”, “any”, “all”, “binary” or
     “full”) in dpkg-genchanges and dpkg-buildpackage.
   * Add new -I option to dpkg-shlibdeps to ignore package build directories.
     Closes: #821025
   * Add new -O option to dpkg-genchanges.
   * Make dpkg export variable DPKG_ROOT in maintainer scripts. Closes: #804624
     Thanks to Helmut Grohne <helmut@subdivi.de>.
   * Add new --force-script-chrootless option to dpkg.
     Thanks to Helmut Grohne <helmut@subdivi.de>.
   * Portability:
     - Move DPKG_ADMINDIR environment variable name out from update-alternatives
       code, to make life easier for non-dpkg-based systems.
     - Move alternatives temporary extension out from update-alternatives code,
       to make life easier for non-dpkg-based systems.
     - Switch start-stop-daemon on */kFreeBSD to use the low-level sysctl(3)
       interface instead of libkvm-dev.
   * Perl modules:
     - Add new CTRL_REPO_RELEASE control block type to Dpkg::Control.
     - Add new CTRL_COPYRIGHT_HEADER, CTRL_COPYRIGHT_FILES and
       CTRL_COPYRIGHT_LICENSE control block types to Dpkg::Control.
     - Make patching a file multiple times fatal for the first quilt patch in
       Dpkg::Source. Reported by Apollon Oikonomopoulos <apoikos@debian.org>.
       Closes: #810720
     - Only warn once when a diff patches a file multiple times in
       Dpkg::Source::Patch, and fix the warning message to make it clear that
       the diff might be patching the file more than once, not just twice.
     - Check existence of search criteria in Dpkg::Index when checking with a
       regex or a string match. Closes: #780906
       Base on a patch by Daniel Dehennin <daniel.dehennin@baby-gnu.org>.
     - Add new functions to validate and parse architecture names in Dpkg::Arch.
     - Make the dependency parser more strict in Dpkg::Deps. Closes: #784806
     - Add strong digest marking support to Dpkg::Checksums.
     - Error out on source packages without any strong digests in
       Dpkg::Source::Package, used by dpkg-source --extract, which can still
       be disabled with --no-check.
     - Switch Dpkg::Conf implementation to be hash based, add two new accessors
       and a new option to the filter method to use the old behavior.
     - Do not parse entry multiple times in Dpkg::Changelog::Entry::Debian.
       Add new parse_header() and parse_trailer() methods, and deprecate
       check_header() and check_trailer() ones.
     - Use “GnuPG” instead of “gpg” in error messages to refer to the software
       in Dpkg::Source::Package.
     - Handle undef versions in Dpkg::Changelog from empty versions in
       changelog entry header lines.
     - Allow detached upstream orig tarball signatures when extracting
       version 1.0 non-native source packages.
     - Include upstream orig tarball signatures in source packages.
       See #759478.
     - Add fixdebugpath to reproducible feature in Dpkg::Vendor::Debian.
       Thanks to Daniel Kahn Gillmor <dkg@fifthhorseman.net>. Closes: #819194
   * Build system:
     - Fix building development documentation.
     - Remove unused UA_LIBS variable.
     - Split libps and libkvm detection into their own macros and variables.
     - Make it possible to build without system libmd.
     - Add a configuration summary to configure output.
     - Make git log invocation immune to local configuration.
     - Do not require passing the perl interpreter to run-script.
     - Quote dirname argument in run-script, to handle spaces in pathname.
       Reported by Carsten Hey <carsten@debian.org>.
     - Use a single po4a opt argument instead of the same per language.
   * Packaging:
     - Enable all hardening flags, starting with gcc-5 there is no performance
       loss anymore when enabling PIE on i386.
   * Test suite:
     - Add a unit test to compile perl code with warnings.
     - Add a unit test for the trigger deferred parser.
   * Documentation:
     - Say value instead of option in deb-control(5).
     - Mark debian changelog format in bold in dpkg-parsechangelog(1).
     - Add references to man pages describing file formats.
     - Document missing Install-Size, Built-For-Profiles and Build-Profiles
       fields in man pages.
     - Add new dsc(5), deb-changelog(5) and deb-changes(5) man pages.
     - Remove Debian specific policy references.
     - Remove superfluous SEE ALSO references from dpkg-source(1).
     - Fix --remove and --purge summary formatting in dpkg(1).
     - Move --audit description just after --verify in dpkg(1).
     - Mark Maintainer field as bold in deb-src-control(5).
     - Fix reference to --record-avail instead of nonexistent --avail.
     - Add missing quotes in man pages.
     - Document Source field version in deb-control(5).
     - Add new deb822(5) man page.
     - Document and improve C/C++ programs exit codes in man pages.
     - Clarify dpkg --path-exclude/--path-include pathname filter behavior.
       Closes: #811267
     - Clarify that packages are only automatically forgotten by dpkg if they
       contain no user data, such as package selections. Closes: #813179
     - Fix documentation for package flags in dpkg(1).
     - Clarify that deb-symbols(5) documents the binary format subset, and
       the template symbol files are described in dpkg-gensymbols(1).
       Closes: #795163
     - Update field requirements of control file formats to match dpkg reality.
     - Document the format of the origins filename in deb-origin(5).
     - Add list of flags set by bug feature area to dpkg-buildflags(1).
     - Switch output encoding of man pages to UTF-8.
     - Move SEE ALSO section to the end of Dpkg::Changelog::Debian.
     - Clarify that i386 does not suffer performance loss due to PIE anymore
       since gcc >= 5 in dpkg-buildflags(1).
     - Document in deb822(5) that deb-origin(5) also supports comments.
     - Clarify which characters constitute the deb822(5) control files syntax
       by using Unicode code points and their printable characters.
       Based on a patch by Ben Finney <ben@benfinney.id.au>.
     - Remove wrong mention that deb-control(5) support comments.
     - Make explicit that deb-control(5) documents the binary control file.
     - Add missing value for Standards-Version field in dsc(5).
       Reported by Helge Kreutzmann <debian@helgefjell.de>.
 .
   [ Updated programs translations ]
   * Dutch (Frans Spiesschaert). Closes: #822797
   * German (Sven Joachim).
   * Japanese (Takuma Yamada). Closes: #819939
   * Portuguese (Miguel Figueiredo).
   * Simplified Chinese (Zhou Mo). Closes: #809517
   * Vietnamese (Trần Ngọc Quân).
 .
   [ Updated dselect translations ]
   * Japanese (Takuma Yamada). Closes: #819940
 .
   [ Updated scripts translations ]
   * German (Helge Kreutzmann).
 .
   [ New manpages translations ]
   * Dutch (Frans Spiesschaert). Closes: #822798
 .
   [ Updated manpages translations ]
   * German (Helge Kreutzmann).
Checksums-Sha1:
 260978c36020a0cf3ea5a3e6ef2d56e6943d10eb 2026 dpkg_1.18.5.dsc
 706adb4b7bdbd195d71d0fc1f9864434b6e869f0 4616552 dpkg_1.18.5.tar.xz
Checksums-Sha256:
 3545dff3478c04ddc4c90901df48df81c9b72872f81d5fb36c45dce1a7d442d9 2026 dpkg_1.18.5.dsc
 074e6a66a1e7a4b14ec3aa1d198be565acff3e067595fd42bb4dec4d14468b07 4616552 dpkg_1.18.5.tar.xz
Files:
 5b2f82bd2cef925f99850703dea57630 2026 admin required dpkg_1.18.5.dsc
 43370c852daf8bcdcdfcc34b5dde22f1 4616552 admin required dpkg_1.18.5.tar.xz

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQIcBAEBCgAGBQJXJslWAAoJELlyvz6krlejMeAQAJoUKwWdMX2YWQpU93CE08vn
BZ3Xl9TcT3vK1az1nrQFMFs0Boxe43c0W7lMdyIYqrc+CbgDNkPBZCnRxO8R+xOa
ue7h6d3EIcGtq+qe8iP2RidnQwfNldzZfb0WmV/lmpECn4FL0xAbnF4+euCQjrsR
WvP7HFNWpcLGwrNM7t4ATbkFSKqCgRQS5yy9bA4b6nFavjXq4Y4FyhsQwu9e3u37
8a4ulasK0CSkJofQ/U7crgpjzHLXjciFcrWfC4Mx9c2dgbvOcvCF5dbjam+1/rsl
gDhNXEG35tlbXtCeDBu/qefontrK6ZS7l2sEmWoNVoZYtdewjJQzZuhtabTcJRo8
nTnJ8mD3oZVNaeKP+csQz1cMAC289hmleX8A0A8vts4fH+HfFZ6/mZf3gbsEc062
VfXXIl9bsPVneljcR2g0PUaPYzHArVfzKywt4ZeEcJgUso/GqySQiA7Fh9xl7BOL
AkKTpNhtM0Tl/nFOIbX1zShCPKcNSEx9YpkzxWFHvLCT9GNWx0eAZHJrw9w7O3lj
tHAAxdxC0vjOpk2Pv0J4t42JCNr0xjrzNdZn7g8tkahYRgGMbHrGDiIH7UmJTDuJ
OYsEB75cSc1QwdqtdtRYYmOxAGVjrfYF1q/DWO7wOmWDGu1Nti/PUkYacG9gEP6z
+jFM/DTpf7Bv7hwRTQyq
=L/BK
-----END PGP SIGNATURE-----

Send a report that this bug log contains spam.