librazor/merger.c
author J. Ali Harlow <ali@juiblex.co.uk>
Thu Feb 09 20:45:27 2012 +0000 (2012-02-09)
changeset 418 33b825d3128d
parent 395 ed134fdfe95f
child 438 fab0b8a61dcb
permissions -rw-r--r--
Add transaction barriers
These allow packages to be installed and removed which have scripts
that depend on each other when atomic transactions are involved.
Note that yum supports pre, but not other requires flags. post will
need similar support to the post scripts themselves pulling in the
requires flags from the rpms. Likewise preun and postun will need
similar handling to those scrips since the requires flags will need
to be stored in the razor database.
     1 /*
     2  * Copyright (C) 2008  Kristian Høgsberg <krh@redhat.com>
     3  * Copyright (C) 2008  Red Hat, Inc
     4  * Copyright (C) 2009-2011  J. Ali Harlow <ali@juiblex.co.uk>
     5  *
     6  * This program is free software; you can redistribute it and/or modify
     7  * it under the terms of the GNU General Public License as published by
     8  * the Free Software Foundation; either version 2 of the License, or
     9  * (at your option) any later version.
    10  *
    11  * This program is distributed in the hope that it will be useful,
    12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    14  * GNU General Public License for more details.
    15  *
    16  * You should have received a copy of the GNU General Public License along
    17  * with this program; if not, write to the Free Software Foundation, Inc.,
    18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
    19  */
    20 
    21 #include <string.h>
    22 #include <assert.h>
    23 #include "razor-internal.h"
    24 #include "razor.h"
    25 
    26 #define UPSTREAM_SOURCE 0x80
    27 
    28 struct source {
    29 	struct razor_set *set;
    30 	uint32_t *property_map;
    31 	uint32_t *file_map;
    32 };
    33 
    34 struct razor_merger {
    35 	int committed;
    36 	struct razor_set *set;
    37 	struct hashtable table;
    38 	struct hashtable file_table;
    39 	struct hashtable details_table;
    40 	struct source source1;
    41 	struct source source2;
    42 };
    43 
    44 struct razor_merger *
    45 razor_merger_create(struct razor_set *set1, struct razor_set *set2)
    46 {
    47 	struct razor_merger *merger;
    48 	int count;
    49 	size_t size;
    50 	uint32_t header_version;
    51 
    52 	merger = zalloc(sizeof *merger);
    53 	merger->set = razor_set_create();
    54 	if (set1->packages.size) {
    55 		header_version = razor_set_get_header_version(set1);
    56 		if (set2->packages.size &&
    57 		    razor_set_get_header_version(set2) > header_version)
    58 			header_version = razor_set_get_header_version(set2);
    59 	} else
    60 		header_version = razor_set_get_header_version(set2);
    61 	razor_set_set_header_version(merger->set, header_version);
    62 	hashtable_init(&merger->table, &merger->set->string_pool);
    63 	hashtable_init(&merger->file_table, &merger->set->file_string_pool);
    64 	hashtable_init(&merger->details_table,
    65 		       &merger->set->details_string_pool);
    66 
    67 	merger->source1.set = set1;
    68 	count = set1->properties.size / sizeof (struct razor_property);
    69 	size = count * sizeof merger->source1.property_map[0];
    70 	merger->source1.property_map = zalloc(size);
    71 	count = set1->files.size / sizeof (struct razor_entry);
    72 	size = count * sizeof merger->source1.file_map[0];
    73 	merger->source1.file_map = zalloc(size);
    74 
    75 	merger->source2.set = set2;
    76 	count = set2->properties.size / sizeof (struct razor_property);
    77 	size = count * sizeof merger->source2.property_map[0];
    78 	merger->source2.property_map = zalloc(size);
    79 	count = set2->files.size / sizeof (struct razor_entry);
    80 	size = count * sizeof merger->source2.file_map[0];
    81 	merger->source2.file_map = zalloc(size);
    82 
    83 	return merger;
    84 }
    85 
    86 void
    87 razor_merger_add_package(struct razor_merger *merger,
    88 			 struct razor_package *package)
    89 {
    90 	char *pool, *details_pool, *s;
    91 	struct list *r;
    92 	struct razor_package *p;
    93 	struct razor_set *set1;
    94 	struct source *source;
    95 	uint32_t flags, *prefix;
    96 	struct array install_prefixes;
    97 
    98 	assert(merger->committed == 0);
    99 
   100 	set1 = merger->source1.set;
   101 	if (set1->packages.data <= (void *) package &&
   102 	    (void *) package < set1->packages.data + set1->packages.size) {
   103 		source = &merger->source1;
   104 		flags = 0;
   105 	} else {
   106 		source = &merger->source2;
   107 		flags = UPSTREAM_SOURCE;
   108 	}
   109 
   110 	pool = source->set->string_pool.data;
   111 	details_pool = source->set->details_string_pool.data;
   112 	p = array_add(&merger->set->packages, sizeof *p);
   113 	p->name = hashtable_tokenize(&merger->table, &pool[package->name]);
   114 	p->flags = flags;
   115 	p->version = hashtable_tokenize(&merger->table,
   116 					&pool[package->version]);
   117 	p->arch = hashtable_tokenize(&merger->table,
   118 				     &pool[package->arch]);
   119 	if (source->set->details_string_pool.size) {
   120 		p->summary = hashtable_tokenize(&merger->details_table,
   121 						&details_pool[package->summary]);
   122 		p->description = hashtable_tokenize(&merger->details_table,
   123 						    &details_pool[package->description]);
   124 		p->url = hashtable_tokenize(&merger->details_table,
   125 					    &details_pool[package->url]);
   126 		p->license = hashtable_tokenize(&merger->details_table,
   127 						&details_pool[package->license]);
   128 	} else {
   129 		p->summary = hashtable_tokenize(&merger->details_table, "");
   130 		p->description = hashtable_tokenize(&merger->details_table, "");
   131 		p->url = hashtable_tokenize(&merger->details_table, "");
   132 		p->license = hashtable_tokenize(&merger->details_table, "");
   133 	}
   134 
   135 	p->properties = package->properties;
   136 	r = list_first(&package->properties, &source->set->property_pool);
   137 	while (r) {
   138 		source->property_map[r->data] = 1;
   139 		r = list_next(r);
   140 	}
   141 
   142 	p->files = package->files;
   143 	r = list_first(&package->files, &source->set->file_pool);
   144 	while (r) {
   145 		source->file_map[r->data] = 1;
   146 		r = list_next(r);
   147 	}
   148 
   149 	array_init(&install_prefixes);
   150 	r = list_first(&package->install_prefixes, &source->set->prefix_pool);
   151 	while (r) {
   152 		s = (char *)source->set->string_pool.data + r->data;
   153 		prefix = array_add(&install_prefixes, sizeof *prefix);
   154 		*prefix = hashtable_tokenize(&merger->table, s);
   155 		r = list_next(r);
   156 	}
   157 	list_set_array(&p->install_prefixes, &merger->set->prefix_pool,
   158                        &install_prefixes, 0);
   159 	array_release(&install_prefixes);
   160 
   161 	p->preun.program = hashtable_tokenize(&merger->table,
   162 					      &pool[package->preun.program]);
   163 	p->preun.body = hashtable_tokenize(&merger->table,
   164 					   &pool[package->preun.body]);
   165 	p->postun.program = hashtable_tokenize(&merger->table,
   166 					       &pool[package->postun.program]);
   167 	p->postun.body = hashtable_tokenize(&merger->table,
   168 					    &pool[package->postun.body]);
   169 }
   170 
   171 static uint32_t
   172 add_property(struct razor_merger *merger,
   173 	     const char *name, uint32_t flags, const char *version)
   174 {
   175 	struct razor_property *p;
   176 
   177 	p = array_add(&merger->set->properties, sizeof *p);
   178 	p->name = hashtable_tokenize(&merger->table, name);
   179 	p->flags = flags;
   180 	p->version = hashtable_tokenize(&merger->table, version);
   181 
   182 	return p - (struct razor_property *) merger->set->properties.data;
   183 }
   184 
   185 static void
   186 merge_properties(struct razor_merger *merger)
   187 {
   188 	struct razor_property *p1, *p2;
   189 	struct razor_set *set1, *set2;
   190 	uint32_t *map1, *map2;
   191 	int i, j, cmp, count1, count2;
   192 	char *pool1, *pool2;
   193 
   194 	set1 = merger->source1.set;
   195 	set2 = merger->source2.set;
   196 	map1 = merger->source1.property_map;
   197 	map2 = merger->source2.property_map;
   198 
   199 	i = 0;
   200 	j = 0;
   201 	pool1 = set1->string_pool.data;
   202 	pool2 = set2->string_pool.data;
   203 
   204 	count1 = set1->properties.size / sizeof *p1;
   205 	count2 = set2->properties.size / sizeof *p2;
   206 	while (i < count1 || j < count2) {
   207 		if (i < count1 && map1[i] == 0) {
   208 			i++;
   209 			continue;
   210 		}
   211 		if (j < count2 && map2[j] == 0) {
   212 			j++;
   213 			continue;
   214 		}
   215 		p1 = (struct razor_property *) set1->properties.data + i;
   216 		p2 = (struct razor_property *) set2->properties.data + j;
   217 		if (i < count1 && j < count2)
   218 			cmp = strcmp(&pool1[p1->name], &pool2[p2->name]);
   219 		else if (i < count1)
   220 			cmp = -1;
   221 		else
   222 			cmp = 1;
   223 		if (cmp == 0)
   224 			cmp = p1->flags - p2->flags;
   225 		if (cmp == 0)
   226 			cmp = razor_versioncmp(&pool1[p1->version],
   227 					       &pool2[p2->version]);
   228 		if (cmp < 0) {
   229 			map1[i++] = add_property(merger,
   230 						 &pool1[p1->name],
   231 						 p1->flags,
   232 						 &pool1[p1->version]);
   233 		} else if (cmp > 0) {
   234 			map2[j++] = add_property(merger,
   235 						 &pool2[p2->name],
   236 						 p2->flags,
   237 						 &pool2[p2->version]);
   238 		} else  {
   239 			map1[i++] = map2[j++] =
   240 				add_property(merger,
   241 					     &pool1[p1->name],
   242 					     p1->flags,
   243 					     &pool1[p1->version]);
   244 		}
   245 	}
   246 }
   247 
   248 static void
   249 emit_properties(struct list_head *properties, struct array *source_pool,
   250 		uint32_t *map, struct array *pool)
   251 {
   252 	uint32_t r;
   253 	struct list *p, *q;
   254 
   255 	r = pool->size / sizeof *q;
   256 	p = list_first(properties, source_pool);
   257 	while (p) {
   258 		q = array_add(pool, sizeof *q);
   259 		q->data = map[p->data];
   260 		q->flags = p->flags;
   261 		p = list_next(p);
   262 	}
   263 
   264 	list_set_ptr(properties, r);
   265 }
   266 
   267 static uint32_t
   268 add_file(struct razor_merger *merger, const char *name)
   269 {
   270 	struct razor_entry *e;
   271 
   272 	e = array_add(&merger->set->files, sizeof *e);
   273 	e->name = hashtable_tokenize(&merger->file_table, name);
   274 	e->flags = 0;
   275 	e->start = 0;
   276 
   277 	return e - (struct razor_entry *)merger->set->files.data;
   278 }
   279 
   280 /* FIXME. Blah */
   281 static int
   282 fix_file_map(uint32_t *map,
   283 	     struct razor_entry *files,
   284 	     struct razor_entry *top)
   285 {
   286 	uint32_t e;
   287 	int found_file = 0;
   288 
   289 	e = top - files;
   290 	do {
   291 		if (files[e].start &&
   292 		    fix_file_map(map, files, &files[files[e].start]))
   293 			map[e] = 1;
   294 		if (map[e])
   295 			found_file = 1;
   296 	} while (!(files[e++].flags & RAZOR_ENTRY_LAST));
   297 
   298 	return found_file;
   299 }
   300 
   301 struct merge_directory {
   302 	uint32_t merged, dir1, dir2;
   303 };
   304 
   305 static void
   306 merge_one_directory(struct razor_merger *merger, struct merge_directory *md)
   307 {
   308 	struct razor_entry *root1, *root2, *mroot, *e1, *e2;
   309 	struct razor_set *set1, *set2;
   310 	struct array merge_stack;
   311 	struct merge_directory *child_md, *end_md;
   312 	uint32_t *map1, *map2, start, last;
   313 	int cmp;
   314 	char *pool1, *pool2;
   315 
   316 	set1 = merger->source1.set;
   317 	set2 = merger->source2.set;
   318 	map1 = merger->source1.file_map;
   319 	map2 = merger->source2.file_map;
   320 	pool1 = set1->file_string_pool.data;
   321 	pool2 = set2->file_string_pool.data;
   322 	root1 = (struct razor_entry *) set1->files.data;
   323 	root2 = (struct razor_entry *) set2->files.data;
   324 
   325 	array_init(&merge_stack);
   326 
   327 	start = merger->set->files.size / sizeof (struct razor_entry);
   328 	last = 0xFFFFFFFF;
   329 	e1 = md->dir1 != 0xFFFFFFFF ? root1 + md->dir1 : NULL;
   330 	e2 = md->dir2 != 0xFFFFFFFF ? root2 + md->dir2 : NULL;
   331 	while (e1 || e2) {
   332 		if (!e2 && !map1[e1 - root1]) {
   333 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   334 				e1 = NULL;
   335 			continue;
   336 		}
   337 		if (!e1 && !map2[e2 - root2]) {
   338 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   339 				e2 = NULL;
   340 			continue;
   341 		}
   342 		if (e1 && !map1[e1 - root1] &&
   343 		    e2 && !map2[e2 - root2]) {
   344 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   345 				e1 = NULL;
   346 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   347 				e2 = NULL;
   348 			continue;
   349 		}
   350 
   351 		if (!e1)
   352 			cmp = 1;
   353 		else if (!e2)
   354 			cmp = -1;
   355 		else {
   356 			cmp = strcmp (&pool1[e1->name],
   357 				      &pool2[e2->name]);
   358 		}
   359 
   360 		if (cmp < 0) {
   361 			if (map1[e1 - root1]) {
   362 				map1[e1 - root1] = last =
   363 					add_file(merger, &pool1[e1->name]);
   364 				if (e1->start) {
   365 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   366 					child_md->merged = last;
   367 					child_md->dir1 = e1->start;
   368 					child_md->dir2 = 0xFFFFFFFF;
   369 				}
   370 			}
   371 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   372 				e1 = NULL;
   373 		} else if (cmp > 0) {
   374 			if (map2[e2 - root2]) {
   375 				map2[e2 - root2] = last =
   376 					add_file(merger, &pool2[e2->name]);
   377 				if (e2->start) {
   378 					child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   379 					child_md->merged = last;
   380 					child_md->dir1 = 0xFFFFFFFF;
   381 					child_md->dir2 = e2->start;
   382 				}
   383 			}
   384 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   385 				e2 = NULL;
   386 		} else {
   387 			map1[e1 - root1] = map2[e2- root2] = last =
   388 				add_file(merger, &pool1[e1->name]);
   389 			if (e1->start || e2->start) {
   390 				child_md = array_add(&merge_stack, sizeof (struct merge_directory));
   391 				child_md->merged = last;
   392 				child_md->dir1 = e1->start ? e1->start : 0xFFFFFFFF;
   393 				child_md->dir2 = e2->start ? e2->start : 0xFFFFFFFF;
   394 			}
   395 			if ((e1++)->flags & RAZOR_ENTRY_LAST)
   396 				e1 = NULL;
   397 			if ((e2++)->flags & RAZOR_ENTRY_LAST)
   398 				e2 = NULL;
   399 		}
   400 	}
   401 
   402 	mroot = (struct razor_entry *)merger->set->files.data;
   403 	if (last != 0xFFFFFFFF) {
   404 		mroot[last].flags = RAZOR_ENTRY_LAST;
   405 		mroot[md->merged].start = start;
   406 	}
   407 
   408 	end_md = merge_stack.data + merge_stack.size;
   409 	for (child_md = merge_stack.data; child_md < end_md; child_md++)
   410 		merge_one_directory(merger, child_md);
   411 	array_release(&merge_stack);
   412 }
   413 
   414 static void
   415 merge_files(struct razor_merger *merger)
   416 {
   417 	struct razor_entry *root;
   418 	struct merge_directory md;
   419 	uint32_t *map1, *map2;
   420 
   421 	map1 = merger->source1.file_map;
   422 	map2 = merger->source2.file_map;
   423 
   424 	md.merged = 0;
   425 
   426 	if (merger->source1.set->files.size) {
   427 		root = (struct razor_entry *) merger->source1.set->files.data;
   428 		if (root->start)
   429 			fix_file_map(map1, root, root);
   430 		md.dir1 = 0;
   431 	} else {
   432 		md.dir1 = 0xFFFFFFFF;
   433 	}
   434 
   435 	if (merger->source2.set->files.size) {
   436 		root = (struct razor_entry *) merger->source2.set->files.data;
   437 		if (root->start)
   438 			fix_file_map(map2, root, root);
   439 		md.dir2 = 0;
   440 	} else {
   441 		md.dir2 = 0xFFFFFFFF;
   442 	}
   443 
   444 	/* Remove the unnamed root which razor_set_create() added */
   445 	array_release(&merger->set->files);
   446 	array_init(&merger->set->files);
   447 
   448 	merge_one_directory(merger, &md);
   449 }
   450 
   451 static void
   452 emit_files(struct list_head *files, struct array *source_pool,
   453 	   uint32_t *map, struct array *pool)
   454 {
   455 	uint32_t r;
   456 	struct list *p, *q;
   457 
   458 	r = pool->size / sizeof *q;
   459 	p = list_first(files, source_pool);
   460 	while (p) {
   461 		q = array_add(pool, sizeof *q);
   462 		q->data = map[p->data];
   463 		q->flags = p->flags;
   464 		p = list_next(p);
   465 	}
   466 
   467 	list_set_ptr(files, r);
   468 }
   469 
   470 /* Rebuild property->packages maps.  We can't just remap these, as a
   471  * property may have lost or gained a number of packages.  Allocate an
   472  * array per property and loop through the packages and add them to
   473  * the arrays for their properties. */
   474 static void
   475 rebuild_property_package_lists(struct razor_set *set)
   476 {
   477 	struct array *pkgs, *a;
   478 	struct razor_package *pkg, *pkg_end;
   479 	struct razor_property *prop, *prop_end;
   480 	struct list *r;
   481 	uint32_t *q;
   482 	int count;
   483 
   484 	count = set->properties.size / sizeof (struct razor_property);
   485 	pkgs = zalloc(count * sizeof *pkgs);
   486 	pkg_end = set->packages.data + set->packages.size;
   487 
   488 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
   489 		r = list_first(&pkg->properties, &set->property_pool);
   490 		while (r) {
   491 			q = array_add(&pkgs[r->data], sizeof *q);
   492 			*q = pkg - (struct razor_package *) set->packages.data;
   493 			r = list_next(r);
   494 		}
   495 	}
   496 
   497 	prop_end = set->properties.data + set->properties.size;
   498 	a = pkgs;
   499 	for (prop = set->properties.data; prop < prop_end; prop++, a++) {
   500 		list_set_array(&prop->packages, &set->package_pool, a, 0);
   501 		array_release(a);
   502 	}
   503 	free(pkgs);
   504 }
   505 
   506 static void
   507 rebuild_file_package_lists(struct razor_set *set)
   508 {
   509 	struct array *pkgs, *a;
   510 	struct razor_package *pkg, *pkg_end;
   511 	struct razor_entry *entry, *entry_end;
   512 	struct list *r;
   513 	uint32_t *q;
   514 	int count;
   515 
   516 	count = set->files.size / sizeof (struct razor_entry);
   517 	pkgs = zalloc(count * sizeof *pkgs);
   518 	pkg_end = set->packages.data + set->packages.size;
   519 
   520 	for (pkg = set->packages.data; pkg < pkg_end; pkg++) {
   521 		r = list_first(&pkg->files, &set->file_pool);
   522 		while (r) {
   523 			q = array_add(&pkgs[r->data], sizeof *q);
   524 			*q = pkg - (struct razor_package *) set->packages.data;
   525 			r = list_next(r);
   526 		}
   527 	}
   528 
   529 	entry_end = set->files.data + set->files.size;
   530 	a = pkgs;
   531 	for (entry = set->files.data; entry < entry_end; entry++, a++) {
   532 		list_set_array(&entry->packages, &set->package_pool, a, 0);
   533 		array_release(a);
   534 	}
   535 	free(pkgs);
   536 }
   537 
   538 struct razor_set *
   539 razor_merger_commit(struct razor_merger *merger)
   540 {
   541 	struct razor_package *p, *pend;
   542 
   543 	/* As we built the package list, we filled out a bitvector of
   544 	 * the properties that are referenced by the packages in the
   545 	 * new set.  Now we do a parallel loop through the properties
   546 	 * and emit those marked in the bit vector to the new set.  In
   547 	 * the process, we update the bit vector to actually map from
   548 	 * indices in the old property list to indices in the new
   549 	 * property list for both sets. */
   550 
   551 	merge_properties(merger);
   552 	merge_files(merger);
   553 
   554 	/* Now we loop through the packages again and emit the
   555 	 * property lists, remapped to point to the new properties. */
   556 
   557 	pend = merger->set->packages.data + merger->set->packages.size;
   558 	for (p = merger->set->packages.data; p < pend; p++) {
   559 		struct source *src;
   560 
   561 		if (p->flags & UPSTREAM_SOURCE)
   562 			src = &merger->source2;
   563 		else
   564 			src = &merger->source1;
   565 
   566 		emit_properties(&p->properties,
   567 				&src->set->property_pool,
   568 				src->property_map,
   569 				&merger->set->property_pool);
   570 		emit_files(&p->files,
   571 			   &src->set->file_pool,
   572 			   src->file_map,
   573 			   &merger->set->file_pool);
   574 		p->flags &= ~UPSTREAM_SOURCE;
   575 	}
   576 
   577 	rebuild_property_package_lists(merger->set);
   578 	rebuild_file_package_lists(merger->set);
   579 
   580 	merger->committed = 1;
   581 
   582 	return merger->set;
   583 }
   584 
   585 void
   586 razor_merger_package_add_script(struct razor_merger *merger,
   587 				struct razor_package *package,
   588 				enum razor_property_flags script,
   589 				const char *program, const char *body)
   590 {
   591 	uint32_t p, b;
   592 	char *pool;
   593 	struct razor_set *set = merger->set;
   594 	assert ((void *)package >= set->packages.data && \
   595 	    (void *)package < set->packages.data + set->packages.size);
   596 
   597 	p = hashtable_tokenize(&merger->table, program);
   598 	b = hashtable_tokenize(&merger->table, body);
   599 
   600 	pool = merger->set->string_pool.data;
   601 
   602 	switch (script) {
   603 	case RAZOR_PROPERTY_PREUN:
   604 		if (package->preun.program != p) {
   605 			assert(pool[package->preun.program] == '\0');
   606 			package->preun.program = p;
   607 		}
   608 		if (package->preun.body != b) {
   609 			assert(pool[package->preun.body] == '\0');
   610 			package->preun.body = b;
   611 		}
   612 		break;
   613 	case RAZOR_PROPERTY_POSTUN:
   614 		if (package->postun.program != p) {
   615 			assert(pool[package->postun.program] == '\0');
   616 			package->postun.program = p;
   617 		}
   618 		if (package->postun.body != b) {
   619 			assert(pool[package->postun.body] == '\0');
   620 			package->postun.body = b;
   621 		}
   622 		break;
   623 	default:
   624 		break;
   625 	}
   626 }
   627 
   628 void razor_merger_destroy(struct razor_merger *merger)
   629 {
   630 	hashtable_release(&merger->table);
   631 	hashtable_release(&merger->file_table);
   632 	hashtable_release(&merger->details_table);
   633 	free(merger);
   634 }