Rewrite depsolver to use a series of passes over all packages.
The big change is that we follow one step of the depedency chain for
each package to resolve in each iteration, and repeat until there are
no more possible moves. In contrast the old depsolver would try to
follow the dependency chain completely for one package at a time.
This new approach is simpler and faster, and at the same time more
roboust. Instead of knowing how one newly installed package may
affect other packages (obsoleting, pulling in new packages etc), the
new algorithm just looks at the total list of requires, provides,
obsoletes and conflicts after installing new packages.
2 * Copyright (C) 2008 Kristian Høgsberg <krh@redhat.com>
3 * Copyright (C) 2008 Red Hat, Inc
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
26 #include <sys/types.h>
30 #include <arpa/inet.h>
31 #include <rpm/rpmlib.h>
32 #include <rpm/rpmdb.h>
36 #include "razor-internal.h"
38 #define RPM_LEAD_SIZE 96
41 unsigned char magic[4];
42 unsigned char reserved[4];
47 struct rpm_header_index {
55 struct rpm_header *signature;
56 struct rpm_header *header;
64 static struct rpm_header_index *
65 razor_rpm_get_header(struct razor_rpm *rpm, unsigned int tag)
67 struct rpm_header_index *index, *end;
69 index = (struct rpm_header_index *) (rpm->header + 1);
70 end = index + ntohl(rpm->header->nindex);
72 if (ntohl(index->tag) == tag)
81 razor_rpm_get_indirect(struct razor_rpm *rpm,
82 unsigned int tag, unsigned int *count)
84 struct rpm_header_index *index;
86 index = razor_rpm_get_header(rpm, tag);
89 *count = ntohl(index->count);
91 return rpm->pool + ntohl(index->offset);
97 static enum razor_version_relation
98 rpm_to_razor_flags (uint_32 flags)
100 switch (flags & (RPMSENSE_LESS | RPMSENSE_EQUAL | RPMSENSE_GREATER)) {
102 return RAZOR_VERSION_LESS;
103 case RPMSENSE_LESS|RPMSENSE_EQUAL:
104 return RAZOR_VERSION_LESS_OR_EQUAL;
106 return RAZOR_VERSION_EQUAL;
107 case RPMSENSE_GREATER|RPMSENSE_EQUAL:
108 return RAZOR_VERSION_GREATER_OR_EQUAL;
109 case RPMSENSE_GREATER:
110 return RAZOR_VERSION_GREATER;
114 return RAZOR_VERSION_EQUAL;
118 import_properties(struct razor_importer *importer, unsigned long type,
119 struct razor_rpm *rpm,
120 int name_tag, int version_tag, int flags_tag)
122 const char *name, *version;
123 const uint_32 *flags;
125 unsigned int i, count;
127 name = razor_rpm_get_indirect(rpm, name_tag, &count);
131 flags = razor_rpm_get_indirect(rpm, flags_tag, &count);
133 version = razor_rpm_get_indirect(rpm, version_tag, &count);
134 for (i = 0; i < count; i++) {
135 f = rpm_to_razor_flags(ntohl(flags[i]));
136 razor_importer_add_property(importer, name, f, version, type);
137 name += strlen(name) + 1;
138 version += strlen(version) + 1;
143 import_files(struct razor_importer *importer, struct razor_rpm *rpm)
146 const uint32_t *index;
147 unsigned int i, count;
150 /* assert: count is the same for all arrays */
152 index = razor_rpm_get_indirect(rpm, RPMTAG_DIRINDEXES, &count);
153 name = razor_rpm_get_indirect(rpm, RPMTAG_BASENAMES, &count);
154 for (i = 0; i < count; i++) {
155 snprintf(buffer, sizeof buffer,
156 "%s%s", rpm->dirs[ntohl(*index)], name);
157 razor_importer_add_file(importer, buffer);
158 name += strlen(name) + 1;
164 razor_rpm_open(const char *filename)
166 struct razor_rpm *rpm;
167 struct rpm_header_index *base, *index;
169 unsigned int count, i, nindex, hsize;
173 rpm = malloc(sizeof *rpm);
174 memset(rpm, 0, sizeof *rpm);
176 fd = open(filename, O_RDONLY);
178 fprintf(stderr, "couldn't open %s\n", filename);
182 if (fstat(fd, &buf) < 0) {
183 fprintf(stderr, "failed to stat %s (%m)\n", filename);
187 rpm->size = buf.st_size;
188 rpm->map = mmap(NULL, rpm->size, PROT_READ, MAP_PRIVATE, fd, 0);
189 if (rpm->map == MAP_FAILED) {
190 fprintf(stderr, "couldn't mmap %s\n", filename);
195 rpm->signature = rpm->map + RPM_LEAD_SIZE;
196 nindex = ntohl(rpm->signature->nindex);
197 hsize = ntohl(rpm->signature->hsize);
198 rpm->header = (void *) (rpm->signature + 1) +
199 ALIGN(nindex * sizeof *index + hsize, 8);
200 nindex = ntohl(rpm->header->nindex);
201 hsize = ntohl(rpm->header->hsize);
202 rpm->payload = (void *) (rpm->header + 1) +
203 nindex * sizeof *index + hsize;
205 base = (struct rpm_header_index *) (rpm->header + 1);
206 rpm->pool = (void *) base + nindex * sizeof *index;
208 /* Look up dir names now so we can index them directly. */
209 name = razor_rpm_get_indirect(rpm, RPMTAG_DIRNAMES, &count);
211 rpm->dirs = calloc(count, sizeof *rpm->dirs);
212 for (i = 0; i < count; i++) {
214 name += strlen(name) + 1;
217 name = razor_rpm_get_indirect(rpm, RPMTAG_OLDFILENAMES,
220 fprintf(stderr, "old filenames not supported\n");
228 struct cpio_file_header {
247 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
248 #define HEAD_CRC 0x02 /* bit 1 set: header CRC present */
249 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
250 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */
251 #define COMMENT 0x10 /* bit 4 set: file comment present */
252 #define RESERVED 0xE0 /* bits 5..7: reserved */
256 struct razor_rpm *rpm;
258 unsigned char buffer[32768];
263 installer_inflate(struct installer *installer)
268 if (installer->rest > sizeof installer->buffer)
269 length = sizeof installer->buffer;
271 length = installer->rest;
273 installer->stream.next_out = installer->buffer;
274 installer->stream.avail_out = length;
275 err = inflate(&installer->stream, Z_SYNC_FLUSH);
276 if (err != Z_OK && err != Z_STREAM_END) {
277 fprintf(stderr, "inflate error: %d (%m)\n", err);
281 installer->rest -= length;
282 installer->length = length;
288 installer_align(struct installer *installer, size_t size)
290 unsigned char buffer[4];
293 installer->stream.next_out = buffer;
294 installer->stream.avail_out =
295 (size - installer->stream.total_out) & (size - 1);
297 if (installer->stream.avail_out == 0)
300 err = inflate(&installer->stream, Z_SYNC_FLUSH);
301 if (err != Z_OK && err != Z_STREAM_END) {
302 fprintf(stderr, "inflate error: %d (%m)\n", err);
310 create_path(struct installer *installer, const char *path, unsigned int mode)
312 char buffer[PATH_MAX];
316 if (razor_create_dir(installer->root, path) < 0)
319 snprintf(buffer, sizeof buffer, "%s%s", installer->root, path);
321 switch (mode >> 12) {
323 /* FIXME: handle the case where a file is already there. */
324 fd = open(buffer, O_WRONLY | O_CREAT | O_TRUNC, mode & 0x1ff);
326 fprintf(stderr, "failed to create file %s\n", buffer);
329 while (installer->rest > 0) {
330 if (installer_inflate(installer)) {
331 fprintf(stderr, "failed to inflate\n");
334 if (razor_write(fd, installer->buffer,
335 installer->length)) {
336 fprintf(stderr, "failed to write payload\n");
341 fprintf(stderr, "failed to close %s: %m\n", buffer);
346 ret = mkdir(buffer, mode & 0x1ff);
347 if (ret == 0 || errno != EEXIST)
349 if (stat(buffer, &buf) || !S_ISDIR(buf.st_mode)) {
350 /* FIXME: also check that mode match. */
352 "%s exists but is not a directory\n", buffer);
360 printf("%s: unhandled file type %d\n", buffer, mode >> 12);
363 if (installer_inflate(installer)) {
364 fprintf(stderr, "failed to inflate\n");
367 if (installer->length >= sizeof installer->buffer) {
368 fprintf(stderr, "link name too long\n");
371 installer->buffer[installer->length] = '\0';
372 if (symlink((const char *) installer->buffer, buffer)) {
373 fprintf(stderr, "failed to create symlink, %m\n");
378 printf("%s: unknown file type %d\n", buffer, mode >> 12);
384 run_script(struct installer *installer,
385 unsigned int program_tag, unsigned int script_tag)
387 int pid, status, fd[2];
388 const char *script = NULL, *program = NULL;
390 program = razor_rpm_get_indirect(installer->rpm, program_tag, NULL);
391 script = razor_rpm_get_indirect(installer->rpm, script_tag, NULL);
392 if (program == NULL && script == NULL) {
394 } else if (program == NULL) {
399 fprintf(stderr, "failed to create pipe\n");
404 fprintf(stderr, "failed to fork, %m\n");
405 } else if (pid == 0) {
406 if (dup2(fd[0], STDIN_FILENO) < 0) {
407 fprintf(stderr, "failed redirect stdin, %m\n");
410 if (close(fd[0]) < 0 || close(fd[1]) < 0) {
411 fprintf(stderr, "failed to close pipe, %m\n");
414 if (chroot(installer->root) < 0) {
415 fprintf(stderr, "failed to chroot to %s, %m\n",
419 printf("executing program %s in chroot %s\n",
420 program, installer->root);
421 if (execl(program, program, NULL)) {
422 fprintf(stderr, "failed to exec %s, %m\n", program);
426 if (script && razor_write(fd[1], script, strlen(script)) < 0) {
427 fprintf(stderr, "failed to pipe script, %m\n");
430 if (close(fd[0]) || close(fd[1])) {
431 fprintf(stderr, "failed to close pipe, %m\n");
434 if (wait(&status) < 0) {
435 fprintf(stderr, "wait for child failed, %m");
439 printf("script exited with status %d\n", status);
446 installer_init(struct installer *installer)
448 unsigned char *gz_header;
449 int method, flags, err;
451 gz_header = installer->rpm->payload;
452 if (gz_header[0] != 0x1f || gz_header[1] != 0x8b) {
453 fprintf(stderr, "payload section doesn't have gz header\n");
457 method = gz_header[2];
458 flags = gz_header[3];
460 if (method != Z_DEFLATED || flags != 0) {
462 "unknown payload compression method or flags set\n");
466 installer->stream.zalloc = NULL;
467 installer->stream.zfree = NULL;
468 installer->stream.opaque = NULL;
470 installer->stream.next_in = gz_header + 10;
471 installer->stream.avail_in =
472 (installer->rpm->map + installer->rpm->size) -
473 (void *) installer->stream.next_in;
474 installer->stream.next_out = NULL;
475 installer->stream.avail_out = 0;
477 err = inflateInit2(&installer->stream, -MAX_WBITS);
479 fprintf(stderr, "inflateInit error: %d\n", err);
487 installer_finish(struct installer *installer)
491 err = inflateEnd(&installer->stream);
494 fprintf(stderr, "inflateEnd error: %d\n", err);
502 fixed_hex_to_ulong(const char *hex, int length)
507 for (i = 0, l = 0; i < length; i++) {
509 l = l * 16 + hex[i] - '0';
511 l = l * 16 + hex[i] - 'a' + 10;
518 razor_rpm_install(struct razor_rpm *rpm, const char *root)
520 struct installer installer;
521 struct cpio_file_header *header;
528 installer.root = root;
530 /* FIXME: Only do this before a transaction, not per rpm. */
531 if (stat(root, &buf) < 0 || !S_ISDIR(buf.st_mode)) {
533 "root installation directory \"%s\" does not exist\n",
538 if (installer_init(&installer))
541 run_script(&installer, RPMTAG_PREINPROG, RPMTAG_PREIN);
543 while (installer.stream.avail_in > 0) {
544 installer.rest = sizeof *header;
545 if (installer_inflate(&installer))
548 header = (struct cpio_file_header *) installer.buffer;
549 mode = fixed_hex_to_ulong(header->mode, sizeof header->mode);
550 filesize = fixed_hex_to_ulong(header->filesize,
551 sizeof header->filesize);
553 installer.rest = fixed_hex_to_ulong(header->namesize,
554 sizeof header->namesize);
556 if (installer_inflate(&installer) ||
557 installer_align(&installer, 4))
560 path = (char *) installer.buffer;
561 /* This convention is so lame... */
562 if (strcmp(path, "TRAILER!!!") == 0)
565 installer.rest = filesize;
566 if (create_path(&installer, path + 1, mode) < 0)
568 if (installer_align(&installer, 4))
572 if (installer_finish(&installer))
575 run_script(&installer, RPMTAG_POSTINPROG, RPMTAG_POSTIN);
581 razor_rpm_close(struct razor_rpm *rpm)
586 err = munmap(rpm->map, rpm->size);
593 razor_importer_add_rpm(struct razor_importer *importer, struct razor_rpm *rpm)
595 const char *name, *version, *release, *arch;
596 const uint_32 *epoch;
597 char evr[128], buf[16];
599 name = razor_rpm_get_indirect(rpm, RPMTAG_NAME, NULL);
600 epoch = razor_rpm_get_indirect(rpm, RPMTAG_EPOCH, NULL);
601 version = razor_rpm_get_indirect(rpm, RPMTAG_VERSION, NULL);
602 release = razor_rpm_get_indirect(rpm, RPMTAG_RELEASE, NULL);
603 arch = razor_rpm_get_indirect(rpm, RPMTAG_ARCH, NULL);
606 snprintf(buf, sizeof buf, "%u", ntohl(*epoch));
607 razor_build_evr(evr, sizeof evr, buf, version, release);
609 razor_build_evr(evr, sizeof evr, NULL, version, release);
611 razor_importer_begin_package(importer, name, evr, arch);
613 import_properties(importer, RAZOR_PROPERTY_REQUIRES, rpm,
615 RPMTAG_REQUIREVERSION,
616 RPMTAG_REQUIREFLAGS);
618 import_properties(importer, RAZOR_PROPERTY_PROVIDES, rpm,
620 RPMTAG_PROVIDEVERSION,
621 RPMTAG_PROVIDEFLAGS);
623 import_properties(importer, RAZOR_PROPERTY_OBSOLETES, rpm,
625 RPMTAG_OBSOLETEVERSION,
626 RPMTAG_OBSOLETEFLAGS);
628 import_properties(importer, RAZOR_PROPERTY_CONFLICTS, rpm,
630 RPMTAG_CONFLICTVERSION,
631 RPMTAG_CONFLICTFLAGS);
633 import_files(importer, rpm);
635 razor_importer_finish_package(importer);
649 add_properties(struct razor_importer *importer,
650 enum razor_property_type property_type,
651 Header h, int_32 name_tag, int_32 version_tag, int_32 flags_tag)
653 union rpm_entry names, versions, flags;
654 int_32 i, type, count;
656 headerGetEntry(h, name_tag, &type, &names.p, &count);
657 headerGetEntry(h, version_tag, &type, &versions.p, &count);
658 headerGetEntry(h, flags_tag, &type, &flags.p, &count);
660 for (i = 0; i < count; i++)
661 razor_importer_add_property(importer,
663 rpm_to_razor_flags (flags.flags[i]),
669 razor_set_create_from_rpmdb(void)
671 struct razor_importer *importer;
672 rpmdbMatchIterator iter;
674 int_32 type, count, i;
675 union rpm_entry name, epoch, version, release, arch;
676 union rpm_entry basenames, dirnames, dirindexes;
677 char filename[PATH_MAX], evr[128], buf[16];
680 rpmReadConfigFiles(NULL, NULL);
682 if (rpmdbOpen("", &db, O_RDONLY, 0644) != 0) {
683 fprintf(stderr, "cannot open rpm database\n");
687 importer = razor_importer_new();
689 iter = rpmdbInitIterator(db, 0, NULL, 0);
690 while (h = rpmdbNextIterator(iter), h != NULL) {
691 headerGetEntry(h, RPMTAG_NAME, &type, &name.p, &count);
692 headerGetEntry(h, RPMTAG_EPOCH, &type, &epoch.p, &count);
693 headerGetEntry(h, RPMTAG_VERSION, &type, &version.p, &count);
694 headerGetEntry(h, RPMTAG_RELEASE, &type, &release.p, &count);
695 headerGetEntry(h, RPMTAG_ARCH, &type, &arch.p, &count);
697 if (epoch.flags != NULL) {
698 snprintf(buf, sizeof buf, "%u", *epoch.flags);
699 razor_build_evr(evr, sizeof evr,
700 buf, version.string, release.string);
702 razor_build_evr(evr, sizeof evr,
703 NULL, version.string, release.string);
706 razor_importer_begin_package(importer,
707 name.string, evr, arch.string);
709 add_properties(importer, RAZOR_PROPERTY_REQUIRES, h,
711 RPMTAG_REQUIREVERSION,
712 RPMTAG_REQUIREFLAGS);
714 add_properties(importer, RAZOR_PROPERTY_PROVIDES, h,
716 RPMTAG_PROVIDEVERSION,
717 RPMTAG_PROVIDEFLAGS);
719 add_properties(importer, RAZOR_PROPERTY_OBSOLETES, h,
721 RPMTAG_OBSOLETEVERSION,
722 RPMTAG_OBSOLETEFLAGS);
724 add_properties(importer, RAZOR_PROPERTY_CONFLICTS, h,
726 RPMTAG_CONFLICTVERSION,
727 RPMTAG_CONFLICTFLAGS);
729 headerGetEntry(h, RPMTAG_BASENAMES, &type,
730 &basenames.p, &count);
731 headerGetEntry(h, RPMTAG_DIRNAMES, &type,
732 &dirnames.p, &count);
733 headerGetEntry(h, RPMTAG_DIRINDEXES, &type,
734 &dirindexes.p, &count);
735 for (i = 0; i < count; i++) {
736 snprintf(filename, sizeof filename, "%s%s",
737 dirnames.list[dirindexes.flags[i]],
739 razor_importer_add_file(importer, filename);
742 razor_importer_finish_package(importer);
747 return razor_importer_finish(importer);