/*
Copyright(C) 2017, Red Hat, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program 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 General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef _GNU_SOURCE /* We use GNU basename() that doesn't modify the arg */
#error "We need GNU version of basename()!"
#endif
#include <errno.h>
#include <getopt.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <libgen.h>
#include "main.h"
#include "objects.h"
#include "utils.h"
#include "compare.h"
/* diff -u style prefix for tree comparison */
#define ADD_PREFIX "+"
#define DEL_PREFIX "-"
/* Return values for the (_)compare_tree functions */
enum {
COMP_SAME = 0, /* Subtree are equal */
COMP_DIFF, /* Subtree differs, stop the scanning */
COMP_CONT, /* Only offset or alignment change, continue */
};
int comp_return_value(int old, int new) {
switch (new) {
case COMP_DIFF:
return COMP_DIFF;
case COMP_CONT:
if (old != COMP_DIFF)
return COMP_CONT;
case COMP_SAME:
;
}
return old;
}
/*
* Is this symbol a duplicate, i.e. is not the first version of this symbol.
*/
static bool is_duplicate(char *filename)
{
char *base = basename(filename);
char *prefix = NULL, *name = NULL;
int version = 0;
bool ret = (sscanf(base, "%m[a-z]--%m[^.-]-%i.txt",
&prefix, &name, &version) == 3);
free(prefix);
free(name);
return ret;
}
static void _print_node_list(const char *s, const char *prefix,
obj_list_t *list, obj_list_t *last, FILE *stream) {
obj_list_t *l = list;
fprintf(stream, "%s:\n", s);
while (l && l != last) {
obj_print_tree__prefix(l->member, prefix, stream);
l = l->next;
}
}
static void print_node_list(const char *s, const char *prefix,
obj_list_t *list, FILE *stream) {
_print_node_list(s, prefix, list, NULL, stream);
}
/*
* There is some ambiguity here that need to be cleared and a
* hierarchy that need to be explicitly established. The current
* situation is: if there is a real change to the object
* (different name, type...) we return CMP_DIFF; If that's not
* the case, but a referred symbol has changed, we return
* CMP_REFFILE; If that's not the case, but the offset has
* changed, we return CMP_OFFSET. So the current order is
* CMP_DIFF > CMP_REFFILE > CMP_OFFSET > CMP_ALIGNMENT"
* In case of alignment, if the structure alignment has changed,
* only that is reported. If not, then the fields are checked and
* the all the different fields are reported.
*/
typedef enum {
CMP_SAME = 0,
CMP_OFFSET, /* Only the offset has changed */
CMP_DIFF, /* Nodes are differents */
CMP_REFFILE, /* A refered symbol has changed */
CMP_ALIGNMENT, /* An alignment has changed */
} cmp_ret_t;
static int compare_two_files(char *filename, char *newfile, bool follow);
static int cmp_node_reffile(obj_t *o1, obj_t *o2)
{
char *s1 = filenametotype(o1->base_type);
char *s2 = filenametotype(o2->base_type);
int len;
bool ret;
ret = safe_streq(s1, s2);
free(s1);
free(s2);
if (!ret)
return CMP_DIFF;
/*
* Compare the symbol referenced by file, but be careful not
* to follow imaginary declaration path.
*
* TODO: This is quite wasteful. We reopen files and parse
* them again many times.
*/
len = strlen(DECLARATION_PATH);
if (strncmp(o1->base_type, DECLARATION_PATH, len) &&
strncmp(o2->base_type, DECLARATION_PATH, len) &&
compare_two_files(o1->base_type, o2->base_type, true))
return CMP_REFFILE;
return CMP_SAME;
}
static int _cmp_nodes(obj_t *o1, obj_t *o2, bool search)
{
if ((o1->type != o2->type) ||
!safe_streq(o1->name, o2->name) ||
(is_weak(o1) != is_weak(o2)) ||
(is_weak(o1) && is_weak(o2) && !safe_streq(o1->link, o2->link)) ||
((o1->ptr == NULL) != (o2->ptr == NULL)) ||
(has_constant(o1) && (o1->constant != o2->constant)) ||
(has_index(o1) && (o1->index != o2->index)) ||
(is_bitfield(o1) != is_bitfield(o2)) ||
(is_bitfield(o1) && ((o1->last_bit - o1->first_bit) !=
(o2->last_bit - o2->first_bit))))
return CMP_DIFF;
if (o1->type == __type_reffile) {
int ret;
ret = cmp_node_reffile(o1, o2);
if (ret)
return ret;
} else if (!safe_streq(o1->base_type, o2->base_type))
return CMP_DIFF;
if (has_offset(o1) &&
((o1->offset != o2->offset) ||
(is_bitfield(o1) && (o1->first_bit != o2->first_bit)))) {
if (search && o1->name == NULL)
/*
* This field is an unnamed struct or union. When
* searching for a node, avoid to consider the next
* unnamed struct or union to be the same one.
*/
return CMP_DIFF;
return CMP_OFFSET;
}
if (o1->alignment != o2->alignment)
return CMP_ALIGNMENT;
return CMP_SAME;
}
static int cmp_nodes(obj_t *o1, obj_t *o2)
{
return _cmp_nodes(o1, o2, false);
}
typedef enum {
DIFF_INSERT,
DIFF_DELETE,
DIFF_REPLACE,
DIFF_CONT,
} diff_ret_t;
/*
* When field are changed or moved around, there can be several diff
* representations for the change. We are trying to keep the diff as
* small as possible, while keeping most significant changes in term
* of kABI (mainly shifted fields, which most likely indicate that
* some change to the ABI have been overlooked).
*
* This function compare two lists whose first member diverge. We're
* looking at four different scenarios:
* - N fields appears only in list2, then the lists rejoined (insertion)
* - P fields appears only in list1, then the lists rejoined (deletion)
* - Q fields diverges, then the lists rejoined (replacement)
* - the lists never rejoined
*
* Since for the same change, several of the scenarios above might
* represent the change, we choose the one that minimize the diff
* (min(N,P,Q)). So we're looking for the first element of list1 in
* list2, the first element of list2 in list1 or the first line where
* list1 and list2 do not differ, whichever comes first.
*/
static diff_ret_t list_diff(obj_list_t *list1, obj_list_t **next1,
obj_list_t *list2, obj_list_t **next2)
{
obj_t *o1 = list2->member, *o2 = list1->member, *o = o1;
int d1 = 0, d2 = 0, ret;
obj_list_t *next;
next = *next1 = list1;
*next2 = list2;
while (next) {
ret = _cmp_nodes(o, next->member, true);
if (ret == CMP_SAME || ret == CMP_OFFSET
|| ret == CMP_ALIGNMENT) {
if (o == o1)
/* We find the first element of list2
on list1, that is d1 elements have
been removed from list1 */
return DIFF_DELETE;
else
return DIFF_INSERT;
}
if (d1 == d2) {
ret = _cmp_nodes((*next1)->member, (*next2)->member,
true);
if (ret == CMP_SAME || ret == CMP_OFFSET
|| ret == CMP_ALIGNMENT) {
/* d1 fields have been replaced */
return DIFF_REPLACE;
}
}
if (!(*next1) || !((*next1)->next) || (d2 < d1)) {
next = *next2 = (*next2)->next;
o = o2;
d2++;
} else {
next = *next1 = (*next1)->next;
o = o1;
d1++;
}
}
return DIFF_CONT;
}
/*
* We want to show practical output to the user. For instance if a
* struct member type change, we want to show which struct member
* changed type, not that somewhere a "signed int" has been changed
* into a "unsigned bin".
*
* For now, we consider that a useful output should start at a named
* object or at a struct field or var (the field/var itself may be
* unamed, typically when it's an union or struct of alternative
* elements but it most likely contains named element).
*/
static bool worthy_of_print(obj_t *o)
{
return (o->name != NULL) ||
(o->type == __type_struct_member) ||
(o->type == __type_var);
}
static void print_two_nodes(const char *s, obj_t *o1, obj_t *o2, FILE *stream)
{
while (!worthy_of_print(o1)) {
o1 = o1->parent;
o2 = o2->parent;
if ((o1 == NULL) || (o2 == NULL))
fail("No ancestor worthy of print\n");
}
fprintf(stream, "%s:\n", s);
obj_print_tree__prefix(o1, DEL_PREFIX, stream);
obj_print_tree__prefix(o2, ADD_PREFIX, stream);
}
typedef struct compare_config_s {
bool debug;
bool hide_kabi;
bool hide_kabi_new;
bool skip_duplicate; /* Don't show multiple version of a symbol */
int follow;
char *old_dir;
char *new_dir;
char *filename;
char **flist;
int flistsz;
int flistcnt;
int ret;
/*
* The following options allow to hide some symbol changes in
* kABI comparison. Hides...
*/
int no_replaced; /* replaced symbols */
int no_shifted; /* symbols whose offset shifted */
int no_inserted; /* symbols inserted in the middle of a struct/union */
int no_deleted; /* symbols removed in the middle (poke a hole) */
int no_added; /* symbols added at the end of a struct/union... */
int no_removed; /* symbols removed at the end of a struct/union... */
int no_moved_files; /* file that has been moved (or removed) */
} compare_config_t;
compare_config_t compare_config = {false, false, false, false, 0,
NULL, NULL, NULL, NULL,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
static void message_alignment_value(unsigned v, FILE *stream)
{
if (v == 0)
fprintf(stream, "<undefined>");
else
fprintf(stream, "%u", v);
}
static void message_alignment(obj_t *o1, obj_t *o2, FILE *stream)
{
char *part_str;
if (o1->type == __type_struct_member) {
part_str = "field";
} else {
part_str = "symbol";
}
fprintf(stream, "The alignment of %s '%s' has changed from ",
part_str, o1->name);
message_alignment_value(o1->alignment, stream);
fprintf(stream, " to ");
message_alignment_value(o2->alignment, stream);
fprintf(stream, "\n");
}
static int _compare_tree(obj_t *o1, obj_t *o2, FILE *stream)
{
obj_list_t *list1 = NULL, *list2 = NULL;
int ret = COMP_SAME, tmp;
tmp = cmp_nodes(o1, o2);
if (tmp) {
if (tmp == CMP_REFFILE) {
fprintf(stream, "symbol %s has changed\n",
o1->base_type);
ret = COMP_DIFF;
} else if ((tmp == CMP_OFFSET && !compare_config.no_shifted) ||
(tmp == CMP_DIFF && !compare_config.no_replaced)) {
const char *s = (tmp == CMP_OFFSET) ?
"Shifted" : "Replaced";
print_two_nodes(s, o1, o2, stream);
ret = COMP_CONT;
} else if (tmp == CMP_ALIGNMENT) {
message_alignment(o1, o2, stream);
ret = COMP_CONT;
}
if (ret == COMP_DIFF)
return ret;
}
if (o1->member_list)
list1 = o1->member_list->first;
if (o2->member_list)
list2 = o2->member_list->first;
while (list1 && list2) {
if (cmp_nodes(list1->member, list2->member) == CMP_DIFF) {
int index;
obj_list_t *next1, *next2;
index = list_diff(list1, &next1, list2, &next2);
switch (index) {
case DIFF_INSERT:
/* Insertion */
if (!compare_config.no_inserted) {
_print_node_list("Inserted", ADD_PREFIX,
list2, next2, stream);
ret = COMP_DIFF;
}
list2 = next2;
break;
case DIFF_DELETE:
/* Removal */
if (!compare_config.no_deleted) {
_print_node_list("Deleted", DEL_PREFIX,
list1, next1, stream);
ret = COMP_DIFF;
}
list1 = next1;
break;
case DIFF_REPLACE:
/*
* We could print the diff here, but relying on
* the next calls to _compare_tree() to display
* the replaced fields individually works too.
*/
case DIFF_CONT:
/* Nothing to do */
;
}
}
tmp =_compare_tree(list1->member, list2->member, stream);
ret = comp_return_value(ret, tmp);
list1 = list1->next;
list2 = list2->next;
if (!list1 && list2) {
if (!compare_config.no_added) {
print_node_list("Added", ADD_PREFIX,
list2, stream);
ret = COMP_DIFF;
}
return ret;
}
if (list1 && !list2) {
if (!compare_config.no_removed) {
print_node_list("Removed", DEL_PREFIX,
list1, stream);
ret = COMP_DIFF;
}
return ret;
}
}
if (o1->ptr && o2->ptr) {
tmp = _compare_tree(o1->ptr, o2->ptr, stream);
ret = comp_return_value(ret, tmp);
}
return ret;
}
/*
* Compare two symbols and show the difference in a c-like format
*/
static int compare_tree(obj_t *o1, obj_t *o2, FILE *stream)
{
return _compare_tree(o1, o2, stream);
}
static bool push_file(char *filename)
{
int i, sz = compare_config.flistsz;
int cnt = compare_config.flistcnt;
char **flist = compare_config.flist;
for (i = 0; i < cnt; i++)
if (!strcmp(flist[i], filename))
return false;
if (!sz) {
compare_config.flistsz = sz = 16;
compare_config.flist = flist =
safe_zmalloc(16 * sizeof(char *));
}
if (cnt >= sz) {
sz *= 2;
compare_config.flistsz = sz;
compare_config.flist = flist =
safe_realloc(flist, sz * sizeof(char *));
}
flist[cnt] = strdup(filename);
compare_config.flistcnt++;
return true;
}
static void free_files()
{
int i;
for (i = 0; i < compare_config.flistcnt; i++)
free(compare_config.flist[i]);
free(compare_config.flist);
compare_config.flistcnt = compare_config.flistsz = 0;
}
static void compare_usage()
{
printf("Usage:\n"
"\tcompare [options] kabi_dir kabi_dir [kabi_file...]\n"
"\tcompare [options] kabi_file kabi_file\n"
"\nOptions:\n"
" -h, --help:\t\tshow this message\n"
" -k, --hide-kabi:\thide changes made by RH_KABI_REPLACE()\n"
" -n, --hide-kabi-new:\n\t\t\thide the kabi trickery made by"
" RH_KABI_REPLACE, but show the new field\n"
" -d, --debug:\tprint the raw tree\n"
" --follow:\t\tfollow referenced symbols\n"
" --no-offset:\tdon't display the offset of struct fields\n"
" --no-replaced:\thide replaced symbols"
" (symbols that changed, but hasn't moved)\n"
" --no-shifted:\thide shifted symbols"
" (symbol that hasn't changed, but whose offset changed)\n"
" --no-inserted:\t"
"hide symbols inserted in the middle of a struct, union...\n"
" --no-deleted:\t"
"hide symbols removed from the middle of a struct, union...\n"
" --no-added:\t\t"
"hide symbols added at the end of a struct, union...\n"
" --no-removed:\t"
"hide symbols removed from the end of a struct, union...\n"
" --no-moved-files:\thide changes caused by symbols "
"definition moving to another file\n\t\t\t"
"Warning: it also hides symbols that are removed entirely\n"
" -s, --skip-duplicate:\tshow only the first version of a "
"symbol when several exist\n");
exit(1);
}
/*
* Parse two files and compare the resulting tree.
*
* filename: file to compare (relative to compare_config.*_dir)
* newfile: if not NULL, the file to use in compare_config.new_dir,
* otherwise, filename is used for both.
* follow: Are we here because we followed a reference file? If so,
* don't print anything and exit immediately if follow
* option isn't set.
*/
static int compare_two_files(char *filename, char *newfile, bool follow)
{
obj_t *root1, *root2;
char *old_dir = compare_config.old_dir;
char *new_dir = compare_config.new_dir;
char *path1, *path2, *s = NULL, *filename2;
FILE *file1, *file2, *stream;
struct stat fstat;
size_t sz;
int ret = 0, tmp;
if (follow && !compare_config.follow)
return 0;
/* Avoid infinite loop */
if (!push_file(filename))
return 0;
safe_asprintf(&path1, "%s/%s", old_dir, filename);
filename2 = newfile ? newfile : filename;
safe_asprintf(&path2, "%s/%s", new_dir, filename2);
if (stat(path2, &fstat) != 0) {
if (errno == ENOENT) {
/* Don't consider an incomplete definition a change */
if (strncmp(filename2, DECLARATION_PATH,
strlen(DECLARATION_PATH)) &&
!compare_config.no_moved_files) {
ret = EXIT_KABI_CHANGE;
printf("Symbol removed or moved: %s\n",
filename);
}
free(path1);
free(path2);
return ret;
} else {
fail("Failed to stat() file%s: %s\n",
path2, strerror(errno));
}
}
file1 = safe_fopen(path1);
file2 = safe_fopen(path2);
root1 = obj_parse(file1, path1);
root2 = obj_parse(file2, path2);
free(path1);
free(path2);
if (compare_config.hide_kabi) {
obj_hide_kabi(root1, compare_config.hide_kabi_new);
obj_hide_kabi(root2, compare_config.hide_kabi_new);
}
if (compare_config.debug && !follow) {
obj_debug_tree(root1);
obj_debug_tree(root2);
}
if (follow) {
stream = fopen("/dev/null", "w");
if (stream == NULL)
fail("Unable to open /dev/null: %s\n", strerror(errno));
} else {
stream = open_memstream(&s, &sz);
}
tmp = compare_tree(root1, root2, stream);
if (tmp != COMP_SAME) {
if (!follow) {
printf("Changes detected in: %s\n", filename);
fflush(stream);
fputs(s, stdout);
putchar('\n');
}
ret = EXIT_KABI_CHANGE;
}
obj_free(root1);
obj_free(root2);
fclose(file1);
fclose(file2);
fclose(stream);
free(s);
return ret;
}
static walk_rv_t compare_files_cb(char *kabi_path, void *arg)
{
compare_config_t *conf = (compare_config_t *)arg;
char *filename;
if (compare_config.skip_duplicate && is_duplicate(kabi_path))
return WALK_CONT;
/* If conf->*_dir contains slashes, skip them */
filename = kabi_path + strlen(conf->old_dir);
while (*filename == '/')
filename++;
free_files();
if (compare_two_files(filename, NULL, false))
conf->ret = EXIT_KABI_CHANGE;
return WALK_CONT;
}
#define COMPARE_NO_OPT(name) \
{"no-"#name, no_argument, &compare_config.no_##name, 1}
/*
* Performs the compare command
*/
int compare(int argc, char **argv)
{
int opt, opt_index;
char *old_dir, *new_dir;
struct stat sb1, sb2;
struct option loptions[] = {
{"debug", no_argument, 0, 'd'},
{"hide-kabi", no_argument, 0, 'k'},
{"hide-kabi-new", no_argument, 0, 'n'},
{"help", no_argument, 0, 'h'},
{"skip-duplicate", no_argument, 0, 's'},
{"follow", no_argument, &compare_config.follow, 1},
{"no-offset", no_argument, &display_options.no_offset, 1},
COMPARE_NO_OPT(replaced),
COMPARE_NO_OPT(shifted),
COMPARE_NO_OPT(inserted),
COMPARE_NO_OPT(deleted),
COMPARE_NO_OPT(added),
COMPARE_NO_OPT(removed),
{"no-moved-files", no_argument,
&compare_config.no_moved_files, 1},
{0, 0, 0, 0}
};
memset(&display_options, 0, sizeof(display_options));
while ((opt = getopt_long(argc, argv, "dknhs",
loptions, &opt_index)) != -1) {
switch (opt) {
case 0:
break;
case 'd':
compare_config.debug = true;
break;
case 'n':
compare_config.hide_kabi_new = true;
/* fall through */
case 'k':
compare_config.hide_kabi = true;
break;
case 's':
compare_config.skip_duplicate = true;
break;
case 'h':
default:
compare_usage();
}
}
if (argc < optind + 2) {
printf("Wrong number of argument\n");
compare_usage();
}
old_dir = compare_config.old_dir = argv[optind++];
new_dir = compare_config.new_dir = argv[optind++];
if ((stat(old_dir, &sb1) == -1) || (stat(new_dir, &sb2) == -1))
fail("stat failed: %s\n", strerror(errno));
if (S_ISREG(sb1.st_mode) && S_ISREG(sb2.st_mode)) {
char *oldname = basename(old_dir);
char *newname = basename(new_dir);
if (optind != argc) {
printf("Too many arguments\n");
compare_usage();
}
compare_config.old_dir = dirname(old_dir);
compare_config.new_dir = dirname(new_dir);
return compare_two_files(oldname, newname, false);
}
if (!S_ISDIR(sb1.st_mode) || !S_ISDIR(sb2.st_mode)) {
printf("Compare takes two directories or two regular"
" files as arguments\n");
compare_usage();
}
if (optind == argc) {
walk_dir(old_dir, false, compare_files_cb, &compare_config);
return compare_config.ret;
}
while (optind < argc) {
char *path, *filename;
filename = compare_config.filename = argv[optind++];
safe_asprintf(&path, "%s/%s", old_dir, filename);
if (stat(path, &sb1) == -1) {
if (errno == ENOENT)
fail("file does not exist: %s\n", path);
fail("stat failed: %s\n", strerror(errno));
}
if (!S_ISREG(sb1.st_mode)) {
printf("Compare third argument must be a regular file");
compare_usage();
}
free(path);
if (compare_two_files(filename, NULL, false))
compare_config.ret = EXIT_KABI_CHANGE;
}
return compare_config.ret;
}