/usr/bin/sort may be incorrect

[Shigeharu TAKENO]

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

+========================================================+
 Shigeharu TAKENO     NIigata Institute of Technology
                       kashiwazaki,Niigata 945-1195 JAPAN
 shige at iee.niit.ac.jp   TEL(&FAX): +81-257-22-8161
+========================================================+