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

version graph

Package: dpkg; Maintainer for dpkg is Dpkg Developers <debian-dpkg@lists.debian.org>; Source for dpkg is src:dpkg.

Reported by: Asheesh Laroia <asheesh@asheesh.org>

Date: Thu, 15 Aug 2013 23:54:06 UTC

Severity: wishlist

Tags: patch

Found in version dpkg/1.16.10

Reply or subscribe to this bug.

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Thu, 15 Aug 2013 23:54:11 GMT) Full text and rfc822 format available.

Acknowledgement sent to Asheesh Laroia <asheesh@asheesh.org>:
New Bug report received and forwarded. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Thu, 15 Aug 2013 23:54:11 GMT) Full text and rfc822 format available.

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

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.



Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Fri, 16 Aug 2013 06:57:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Guillem Jover <guillem@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Fri, 16 Aug 2013 06:57:04 GMT) Full text and rfc822 format available.

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

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



Severity set to 'wishlist' from 'normal' Request was from Guillem Jover <guillem@debian.org> to 719845-submit@bugs.debian.org. (Fri, 16 Aug 2013 06:57:04 GMT) Full text and rfc822 format available.

Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Fri, 16 Aug 2013 13:09:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Asheesh Laroia <asheesh@asheesh.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Fri, 16 Aug 2013 13:09:04 GMT) Full text and rfc822 format available.

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

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.



Changed Bug title to 'dpkg-deb: Make file order within {data,control}.tar.gz deterministic' from 'dpkg-source: Make file order within {data,control}.tar.gz deterministic' Request was from Guillem Jover <guillem@debian.org> to control@bugs.debian.org. (Mon, 19 Aug 2013 11:03:05 GMT) Full text and rfc822 format available.

Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Thu, 22 Aug 2013 19:21:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Shawn Landden <shawnlandden@gmail.com>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Thu, 22 Aug 2013 19:21:04 GMT) Full text and rfc822 format available.

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

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




Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Thu, 22 Aug 2013 23:03:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Guillem Jover <guillem@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Thu, 22 Aug 2013 23:03:04 GMT) Full text and rfc822 format available.

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

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



Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Thu, 22 Aug 2013 23:09:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Shawn <shawnlandden@gmail.com>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Thu, 22 Aug 2013 23:09:04 GMT) Full text and rfc822 format available.

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

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)]

Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Tue, 27 Aug 2013 21:15:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Jérémy Bobbio <lunar@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Tue, 27 Aug 2013 21:15:04 GMT) Full text and rfc822 format available.

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

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)]

Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Wed, 28 Aug 2013 02:54:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Guillem Jover <guillem@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Wed, 28 Aug 2013 02:54:04 GMT) Full text and rfc822 format available.

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

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



Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Wed, 28 Aug 2013 06:03:04 GMT) Full text and rfc822 format available.

Acknowledgement sent to Jérémy Bobbio <lunar@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Wed, 28 Aug 2013 06:03:04 GMT) Full text and rfc822 format available.

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

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)]

Information forwarded to debian-bugs-dist@lists.debian.org, Dpkg Developers <debian-dpkg@lists.debian.org>:
Bug#719845; Package dpkg. (Fri, 17 Jan 2014 19:36:09 GMT) Full text and rfc822 format available.

Acknowledgement sent to Jérémy Bobbio <lunar@debian.org>:
Extra info received and forwarded to list. Copy sent to Dpkg Developers <debian-dpkg@lists.debian.org>. (Fri, 17 Jan 2014 19:36:09 GMT) Full text and rfc822 format available.

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

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)]

Added tag(s) patch. Request was from Jérémy Bobbio <lunar@debian.org> to 719845-submit@bugs.debian.org. (Fri, 17 Jan 2014 19:36:10 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Wed Apr 16 16:27:54 2014; Machine Name: beach.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.