Re: /usr/bin/sort may be incorrect

Marius Strobl <[email protected]> Mon, 11 Apr 2016 23:57:34 +0200

Newsgroups	gmane.os.freebsd.devel.sparc
Message-ID	<[email protected]>

On Thu, Mar 31, 2016 at 08:22:25PM +0900, Shigeharu TAKENO wrote:
> shige 03/31 2016
> ----------------
> 
> Thank you for your reply.
> 
> Joerg Wunsch wrote:
> 
> | struct key_value
> | {
> |    struct bwstring *k;
> |    struct key_hint hint[];
> | };
> | 
> | If that works for you, too, I think it would be the preferrable way to
> | write it.
> 
> Unfortunately this does not fix the problem.
> 
> 
> | > The k field of key_value may be overwritten by the hint field
> | > in numcoll_impl(), gnumcoll() and monthcoll() (coll.c), and the
> | > pointer value of k may change to incorrect value.
> | 
> | Are you saying that something like
> | 
> | struct key_value *kw;
> | 
> | ...
> | 
> |    kw->hint[-1] = something;
> | 
> | happens?  That would certainly be a bug in the code then that ought to
> | be fixed, rather than worked around.
> 
> I tested under your suggestion "struct key_hint hint[]", which 
> behaves as the same of default sort command.
> 
> % ( echo 2 5 8 ; echo 2 6 5 ) | sort -n +0 -1 +1 -2 +2 -3
> 
> 
> In key_coll(struct keys_array *ps1, struct keys_array *ps2, 
>   size_t offset) (in coll.c), initial pointer values are the
> followings:
> 
>  &(ps1->key[0]) = 0x40c140f8
>  &(ps1->key[1]) = 0x40c14100
>  &(ps1->key[2]) = 0x40c14108
>  &(ps2->key[0]) = 0x40c14088
>  &(ps2->key[1]) = 0x40c14090
>  &(ps2->key[2]) = 0x40c14198
>  (the pointer repeat is only 8 byte.)
> 
>  ps1->key[0].k = 0x40c060e0
>  ps1->key[1].k = 0x40c060f0
>  ps1->key[2].k = 0x40c06100
>  ps2->key[0].k = 0x40c060a0
>  ps2->key[1].k = 0x40c060b0
>  ps2->key[2].k = 0x40c060c0
> 
> key_coll() calls sm->func() = numcoll(), and it uses
> numcoll_impl(struct key_value *kv1, struct key_value *kv2) with
> ps1->key[i] and ps2->key[i]. The function numcoll_impl() uses k
> field and hint field of struct key_value.
> 
> 
> For i = 0, the k field pointers of arguments kv1 and kv2 of 
> numcoll_impl() are correct:
> 
>  kv1->k = 0x40c060e0, kv2->k = 0x40c060a0
> 
> but the hint field pointers of kv1, kv2 are doughtful:
> 
>  &(kv1->hint) = 0x40c14100, &(kv2->hint) = 0x40c14090
> 
> which are the same value of &(ps1->key[1]) and &(ps2->key[1]).
> 
> 
> And for i = 1, the k field pointers of arguments kv1 and kv2 
> become incorrect:
> 
>  kv1->k = 0x140c060f0, kv2->k = 0x140c060b0
> 
> which are added 0x100000000 to the original pointer value. 
> The sort command stops where it uses the value.
> 
> 
> If we use the definition "struct key_hint hint[1]", the repeat
> of pointers of ps1->key[i] becomes 32 byte, and incorrect changes 
> of pointers do not occur.
> 
>   &(ps1->key[0]) = 0x40c08208
>   &(ps1->key[1]) = 0x40c08228
>   &(ps1->key[2]) = 0x40c08248
> 

AFAICT is sort(1) relying on undefined behavior. It builds up an
array of struct keys_array, which in turn has a zero length array
(apparently unnecessary) of struct key_value, which in turn has
a zero length array of struct key_hint. While sort(1) takes care
to allocate space for the latter based on need_hint, it relies
on the compiler to determine the correct offsets of the struct
key_value elements within the array of struct keys_array. Given
that the compiler isn't aware of the actual size - for essentially
the same reason zero length arrays also don't contribute to the
sizeof() of such a struct - of struct key_value, that doesn't
work, i. e. struct key_hint isn't accounted for in the offset
calculation leading to the corruption described above.
I'm not exactly sure why this bug apparently doesn't affect x86
but I think that's due to its little-endian addressing avoiding
corruption in practice; that's somewhat hard to think through
given that struct bwstring and the use thereof are a similarly
... interesting constructs.
Anyway, using an accessor function for determining the correct
offsets of struct key_value elements within the array of struct
keys_array as in the attached patch fixes the problem for me.
However, I suspect that the space savings by only allocating
memory for struct key_hint when needed don't really justify
all the hackery involved in that approach. At least, changing
struct key_hint to be a fixed member of struct key_value and
removing all parts hanging off from need_hint would make the
code a lot cleaner and readable.

Gabor, what do you think?

Marius

sort.diff (text/x-diff, 2.9 KB)

Index: coll.c
===================================================================
--- coll.c	(revision 297803)
+++ coll.c	(working copy)
@@ -105,14 +105,29 @@
 {
 
 	if (ka) {
-		for (size_t i = 0; i < keys_num; ++i)
-			if (ka->key[i].k && ka->key[i].k != s)
-				bwsfree(ka->key[i].k);
+		for (size_t i = 0; i < keys_num; ++i) {
+			const struct key_value *kv;
+
+			kv = get_key_from_keys_array(ka, i);
+			if (kv->k && kv->k != s)
+				bwsfree(kv->k);
+		}
 		memset(ka, 0, keys_array_size());
 	}
 }
 
 /*
+ * Get pointer to a key value in the keys set
+ */
+struct key_value *
+get_key_from_keys_array(struct keys_array *ka, size_t ind)
+{
+
+	return ((struct key_value *)((caddr_t)&(ka->key[ind]) +
+	    (key_hint_size() * ind)));
+}
+
+/*
  * Set value of a key in the keys set
  */
 void
@@ -122,7 +137,7 @@
 	if (ka && keys_num > ind) {
 		struct key_value *kv;
 
-		kv = &(ka->key[ind]);
+		kv = get_key_from_keys_array(ka, ind);
 
 		if (kv->k && kv->k != s)
 			bwsfree(kv->k);
@@ -156,9 +171,9 @@
 		if (si->str)
 			ret += bws_memsize(si->str);
 		for (size_t i = 0; i < keys_num; ++i) {
-			struct key_value *kv;
+			const struct key_value *kv;
 
-			kv = &(si->ka.key[i]);
+			kv = get_key_from_keys_array(&si->ka, i);
 
 			if (kv->k != si->str)
 				ret += bws_memsize(kv->k);
@@ -475,16 +490,19 @@
 int
 key_coll(struct keys_array *ps1, struct keys_array *ps2, size_t offset)
 {
+	struct key_value *kv1, *kv2;
 	struct sort_mods *sm;
 	int res = 0;
 
 	for (size_t i = 0; i < keys_num; ++i) {
+		kv1 = get_key_from_keys_array(ps1, i);
+		kv2 = get_key_from_keys_array(ps2, i);
 		sm = &(keys[i].sm);
 
 		if (sm->rflag)
-			res = sm->func(&(ps2->key[i]), &(ps1->key[i]), offset);
+			res = sm->func(kv2, kv1, offset);
 		else
-			res = sm->func(&(ps1->key[i]), &(ps2->key[i]), offset);
+			res = sm->func(kv1, kv2, offset);
 
 		if (res)
 			break;
Index: coll.h
===================================================================
--- coll.h	(revision 297803)
+++ coll.h	(working copy)
@@ -91,7 +91,7 @@
 {
 	struct bwstring		*k; /* key string */
 	struct key_hint		 hint[0]; /* key sort hint */
-};
+} __packed;
 
 /*
  * Set of keys container object.
@@ -146,6 +146,7 @@
 
 struct keys_array *keys_array_alloc(void);
 size_t keys_array_size(void);
+struct key_value *get_key_from_keys_array(struct keys_array *ka, size_t ind);
 void set_key_on_keys_array(struct keys_array *ka, struct bwstring *s, size_t ind);
 void clean_keys_array(const struct bwstring *s, struct keys_array *ka);
 
Index: radixsort.c
===================================================================
--- radixsort.c	(revision 297803)
+++ radixsort.c	(working copy)
@@ -243,9 +243,11 @@
 static inline int
 get_wc_index(struct sort_list_item *sli, size_t level)
 {
+	const struct key_value *kv;
 	const struct bwstring *bws;
 
-	bws = sli->ka.key[0].k;
+	kv = get_key_from_keys_array(&sli->ka, 0);
+	bws = kv->k;
 
 	if ((BWSLEN(bws) > level))
 		return (unsigned char) BWS_GET(bws,level);

signature.asc (application/pgp-signature, 949 B)