From 3ef06f9901829dc03aaf685faf8612170f4c909c Mon Sep 17 00:00:00 2001 From: Michael Schroeder Date: Mon, 8 Jun 2009 17:20:20 +0200 Subject: [PATCH] - update transaction ordering code - add queue insert/delete functions --- src/queue.c | 51 ++++ src/queue.h | 5 + src/solvable.c | 23 ++ src/transaction.c | 696 ++++++++++++++++++++++++++++++++++++++++++++---------- src/transaction.h | 20 +- 5 files changed, 667 insertions(+), 128 deletions(-) diff --git a/src/queue.c b/src/queue.c index 345050f..38fd765 100644 --- a/src/queue.c +++ b/src/queue.c @@ -75,3 +75,54 @@ queue_alloc_one(Queue *q) } } +void +queue_insert(Queue *q, int pos, Id id) +{ + queue_push(q, id); /* make room */ + if (pos < q->count - 1) + { + memmove(q->elements + pos + 1, q->elements + pos, (q->count - 1 - pos) * sizeof(Id)); + q->elements[pos] = id; + } +} + +void +queue_delete(Queue *q, int pos) +{ + if (pos >= q->count) + return; + if (pos < q->count - 1) + memmove(q->elements + pos, q->elements + pos + 1, (q->count - 1 - pos) * sizeof(Id)); + q->left++; + q->count--; +} + +void +queue_insert2(Queue *q, int pos, Id id1, Id id2) +{ + queue_push(q, id1); /* make room */ + queue_push(q, id2); /* make room */ + if (pos < q->count - 2) + { + memmove(q->elements + pos + 2, q->elements + pos, (q->count - 2 - pos) * sizeof(Id)); + q->elements[pos] = id1; + q->elements[pos] = id2; + } +} + +void +queue_delete2(Queue *q, int pos) +{ + if (pos >= q->count) + return; + if (pos == q->count - 1) + { + q->left++; + q->count--; + return; + } + if (pos < q->count - 2) + memmove(q->elements + pos, q->elements + pos + 2, (q->count - 2 - pos) * sizeof(Id)); + q->left += 2; + q->count -= 2; +} diff --git a/src/queue.h b/src/queue.h index 4b3f9eb..090799e 100644 --- a/src/queue.h +++ b/src/queue.h @@ -106,4 +106,9 @@ extern void queue_init_buffer(Queue *q, Id *buf, int size); extern void queue_init_clone(Queue *t, Queue *s); extern void queue_free(Queue *q); +extern void queue_insert(Queue *q, int pos, Id id); +extern void queue_insert2(Queue *q, int pos, Id id1, Id id2); +extern void queue_delete(Queue *q, int pos); +extern void queue_delete2(Queue *q, int pos); + #endif /* SATSOLVER_QUEUE_H */ diff --git a/src/solvable.c b/src/solvable.c index 68a3855..6f6f590 100644 --- a/src/solvable.c +++ b/src/solvable.c @@ -42,6 +42,29 @@ solvable_lookup_id(Solvable *s, Id keyname) return repo_lookup_id(s->repo, s - s->repo->pool->solvables, keyname); } +int +solvable_lookup_idarray(Solvable *s, Id keyname, Queue *q) +{ + Dataiterator di; + int found = 0; + + queue_empty(q); + if (!s->repo) + return 0; + dataiterator_init(&di, s->repo->pool, s->repo, s - s->repo->pool->solvables, keyname, 0, SEARCH_ARRAYSENTINEL); + while (dataiterator_step(&di)) + { + if (di.key->type != REPOKEY_TYPE_IDARRAY && di.key->type != REPOKEY_TYPE_REL_IDARRAY) + continue; + found = 1; + if (di.kv.eof) + break; + queue_push(q, di.kv.id); + } + dataiterator_free(&di); + return found; +} + const char * solvable_lookup_str(Solvable *s, Id keyname) { diff --git a/src/transaction.c b/src/transaction.c index cfedc79..b0cde03 100644 --- a/src/transaction.c +++ b/src/transaction.c @@ -324,6 +324,9 @@ transaction_free(Transaction *trans) queue_free(&trans->transaction_info); trans->transaction_installed = sat_free(trans->transaction_installed); map_free(&trans->transactsmap); + trans->tes = sat_free(trans->tes); + trans->ntes = 0; + trans->invedgedata = sat_free(trans->invedgedata); } void @@ -433,42 +436,84 @@ transaction_calculate(Transaction *trans, Queue *decisionq, Map *noobsmap) #define TYPE_REQ (1<<4) #define TYPE_PREREQ (1<<5) -#define EDGEDATA_BLOCK 127 +#define TYPE_CYCLETAIL (1<<16) +#define TYPE_CYCLEHEAD (1<<17) -struct transel { - Id p; - Id type; - Id edges; - Id invedges; - Id mark; - Id medianr; - Id ddeg; /* unused */ -}; +#define EDGEDATA_BLOCK 127 struct orderdata { Transaction *trans; - struct transel *tes; + struct _TransactionElement *tes; int ntes; Id *edgedata; int nedgedata; Id *invedgedata; - Map cycletes; + + Queue cycles; + Queue cyclesdata; + int ncycles; }; static int +addteedge(struct orderdata *od, int from, int to, int type) +{ + int i; + struct _TransactionElement *te; + + if (from == to) + return 0; + + /* printf("edge %d(%s) -> %d(%s) type %x\n", from, solvid2str(pool, od->tes[from].p), to, solvid2str(pool, od->tes[to].p), type); */ + + te = od->tes + from; + for (i = te->edges; od->edgedata[i]; i += 2) + if (od->edgedata[i] == to) + break; + /* test of brokenness */ + if (type == TYPE_BROKEN) + return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0; + if (od->edgedata[i]) + { + od->edgedata[i + 1] |= type; + return 0; + } + if (i + 1 == od->nedgedata) + { + /* printf("tail add %d\n", i - te->edges); */ + if (!i) + te->edges = ++i; + od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK); + } + else + { + /* printf("extend %d\n", i - te->edges); */ + od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK); + if (i > te->edges) + memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges)); + i = od->nedgedata + (i - te->edges); + te->edges = od->nedgedata; + } + od->edgedata[i] = to; + od->edgedata[i + 1] = type; + od->edgedata[i + 2] = 0; /* end marker */ + od->nedgedata = i + 3; + return 0; +} + +static int addedge(struct orderdata *od, Id from, Id to, int type) { Transaction *trans = od->trans; Pool *pool = trans->pool; Solvable *s; - struct transel *te; + struct _TransactionElement *te; int i; // printf("addedge %d %d type %d\n", from, to, type); s = pool->solvables + from; if (s->repo == pool->installed && trans->transaction_installed[from - pool->installed->start]) { - /* passive, map to active */ + /* obsolete, map to install */ if (trans->transaction_installed[from - pool->installed->start] > 0) from = trans->transaction_installed[from - pool->installed->start]; else @@ -488,7 +533,7 @@ addedge(struct orderdata *od, Id from, Id to, int type) s = pool->solvables + to; if (s->repo == pool->installed && trans->transaction_installed[to - pool->installed->start]) { - /* passive, map to active */ + /* obsolete, map to install */ if (trans->transaction_installed[to - pool->installed->start] > 0) to = trans->transaction_installed[to - pool->installed->start]; else @@ -506,7 +551,7 @@ addedge(struct orderdata *od, Id from, Id to, int type) } } - /* map target to te num */ + /* map from/to to te numbers */ for (i = 1, te = od->tes + i; i < od->ntes; i++, te++) if (te->p == to) break; @@ -520,47 +565,10 @@ addedge(struct orderdata *od, Id from, Id to, int type) if (i == od->ntes) return 0; - if (i == to) - return 0; /* no edges to ourselfes */ - - /* printf("edge %d(%s) -> %d(%s) type %x\n", i, solvid2str(pool, od->tes[i].p), to, solvid2str(pool, od->tes[to].p), type); */ - - for (i = te->edges; od->edgedata[i]; i += 2) - if (od->edgedata[i] == to) - break; - /* test of brokenness */ - if (type == TYPE_BROKEN) - return od->edgedata[i] && (od->edgedata[i + 1] & TYPE_BROKEN) != 0 ? 1 : 0; - if (od->edgedata[i]) - { - od->edgedata[i + 1] |= type; - return 0; - } - if (i + 1 == od->nedgedata) - { - /* printf("tail add %d\n", i - te->edges); */ - if (!i) - te->edges = ++i; - od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3, sizeof(Id), EDGEDATA_BLOCK); - } - else - { - /* printf("extend %d\n", i - te->edges); */ - od->edgedata = sat_extend(od->edgedata, od->nedgedata, 3 + (i - te->edges), sizeof(Id), EDGEDATA_BLOCK); - if (i > te->edges) - memcpy(od->edgedata + od->nedgedata, od->edgedata + te->edges, sizeof(Id) * (i - te->edges)); - i = od->nedgedata + (i - te->edges); - te->edges = od->nedgedata; - } - od->edgedata[i] = to; - od->edgedata[i + 1] = type; - od->edgedata[i + 2] = 0; - od->nedgedata = i + 3; - te->ddeg++; - od->tes[to].ddeg--; - return 0; + return addteedge(od, i, to, type); } +#if 1 static int havechoice(struct orderdata *od, Id p, Id q1, Id q2) { @@ -572,7 +580,9 @@ havechoice(struct orderdata *od, Id p, Id q1, Id q2) /* both q1 and q2 are uninstalls. check if their TEs intersect */ /* common case: just one TE for both packages */ +#if 0 printf("havechoice %d %d %d\n", p, q1, q2); +#endif if (trans->transaction_installed[q1 - pool->installed->start] == 0) return 1; if (trans->transaction_installed[q2 - pool->installed->start] == 0) @@ -598,6 +608,34 @@ havechoice(struct orderdata *od, Id p, Id q1, Id q2) queue_free(&ti2); return 1; } +#endif + +static inline int +havescripts(Pool *pool, Id solvid) +{ + Solvable *s = pool->solvables + solvid; + const char *dep; + if (s->requires) + { + Id req, *reqp; + int inpre = 0; + reqp = s->repo->idarraydata + s->requires; + while ((req = *reqp++) != 0) + { + if (req == SOLVABLE_PREREQMARKER) + { + inpre = 1; + continue; + } + if (!inpre) + continue; + dep = id2str(pool, req); + if (*dep == '/' && strcmp(dep, "/sbin/ldconfig") != 0) + return 1; + } + } + return 0; +} static void addsolvableedges(struct orderdata *od, Solvable *s) @@ -610,7 +648,11 @@ addsolvableedges(struct orderdata *od, Solvable *s) Repo *installed = pool->installed; Solvable *s2; Queue reqq; + int provbyinst; +#if 0 + printf("addsolvableedges %s\n", solvable2str(pool, s)); +#endif p = s - pool->solvables; queue_init(&reqq); if (s->requires) @@ -624,8 +666,17 @@ addsolvableedges(struct orderdata *od, Solvable *s) pre = TYPE_PREREQ; continue; } +#if 0 + if (pre != TYPE_PREREQ && installed && s->repo == installed) + { + /* ignore normal requires if we're getting obsoleted */ + if (trans->transaction_installed[p - pool->installed->start]) + continue; + } +#endif queue_empty(&reqq); numins = 0; /* number of packages to be installed providing it */ + provbyinst = 0; /* provided by kept package */ FOR_PROVIDES(p2, pp2, req) { s2 = pool->solvables + p2; @@ -636,8 +687,14 @@ addsolvableedges(struct orderdata *od, Solvable *s) } if (s2->repo == installed && !MAPTST(&trans->transactsmap, p2)) { + provbyinst = 1; +#if 0 + printf("IGNORE inst provides %s by %s\n", dep2str(pool, req), solvable2str(pool, s2)); reqq.count = 0; /* provided by package that stays installed */ break; +#else + continue; +#endif } if (s2->repo != installed && !MAPTST(&trans->transactsmap, p2)) continue; /* package stays uninstalled */ @@ -654,11 +711,40 @@ addsolvableedges(struct orderdata *od, Solvable *s) if (s2->repo == installed) continue; /* s2 gets uninstalled */ queue_pushunique(&reqq, p2); - /* EDGE s(A) -> s2(A) */ } } + if (provbyinst) + { + /* prune to harmless ->inst edges */ + for (i = j = 0; i < reqq.count; i++) + if (pool->solvables[reqq.elements[i]].repo != installed) + reqq.elements[j++] = reqq.elements[i]; + reqq.count = j; + } + if (numins && reqq.count) { + if (s->repo == installed) + { + for (i = 0; i < reqq.count; i++) + { + if (pool->solvables[reqq.elements[i]].repo == installed) + { + for (j = 0; j < reqq.count; j++) + { + if (pool->solvables[reqq.elements[j]].repo != installed) + { + if (trans->transaction_installed[reqq.elements[i] - pool->installed->start] == reqq.elements[j]) + continue; /* no self edge */ +#if 0 + printf("add interrreq uninst->inst edge (%s -> %s -> %s)\n", solvid2str(pool, reqq.elements[i]), dep2str(pool, req), solvid2str(pool, reqq.elements[j])); +#endif + addedge(od, reqq.elements[i], reqq.elements[j], pre == TYPE_PREREQ ? TYPE_PREREQ_P : TYPE_REQ_P); + } + } + } + } + } /* no mixed types, remove all deps on uninstalls */ for (i = j = 0; i < reqq.count; i++) if (pool->solvables[reqq.elements[i]].repo != installed) @@ -678,7 +764,7 @@ addsolvableedges(struct orderdata *od, Solvable *s) if (pool->solvables[p].repo != installed) { #if 0 - printf("add inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2)); + printf("add inst->inst edge choice %d (%s -> %s -> %s)\n", choice, solvid2str(pool, p), dep2str(pool, req), solvid2str(pool, p2)); #endif addedge(od, p, p2, pre); } @@ -692,6 +778,16 @@ addsolvableedges(struct orderdata *od, Solvable *s) } else { + if (s->repo != installed) + continue; /* no inst->uninst edges, please! */ + + /* uninst -> uninst edge. Those make trouble. Only add if we must */ + if (trans->transaction_installed[p - installed->start] && !havescripts(pool, p)) + { + /* p is obsoleted by another package and has no scripts */ + /* we assume that the obsoletor is good enough to replace p */ + continue; + } #if 1 choice = 0; for (j = 0; j < reqq.count; j++) @@ -745,42 +841,20 @@ addsolvableedges(struct orderdata *od, Solvable *s) queue_free(&reqq); } -static inline int -haveprereq(Pool *pool, Id solvid) -{ - Solvable *s = pool->solvables + solvid; - if (s->requires) - { - Id req, *reqp; - int inpre = 0; - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) - { - if (req == SOLVABLE_PREREQMARKER) - { - inpre = 1; - continue; - } - if (inpre && strncmp(id2str(pool, req), "rpmlib(", 7) != 0) - return 1; - } - } - return 0; -} -void +/* break an edge in a cycle */ +static void breakcycle(struct orderdata *od, Id *cycle) { Pool *pool = od->trans->pool; Id ddegmin, ddegmax, ddeg; int k, l; - struct transel *te; + struct _TransactionElement *te; l = 0; ddegmin = ddegmax = 0; for (k = 0; cycle[k + 1]; k += 2) { - MAPSET(&od->cycletes, cycle[k]); /* this te is involved in a cycle */ ddeg = od->edgedata[cycle[k + 1] + 1]; if (ddeg > ddegmax) ddegmax = ddeg; @@ -792,7 +866,7 @@ breakcycle(struct orderdata *od, Id *cycle) } if (ddeg == ddegmin) { - if (haveprereq(pool, od->tes[cycle[l]].p) && !haveprereq(pool, od->tes[cycle[k]].p)) + if (havescripts(pool, od->tes[cycle[l]].p) && !havescripts(pool, od->tes[cycle[k]].p)) { /* prefer k, as l comes from a package with contains scriptlets */ l = k; @@ -803,6 +877,23 @@ breakcycle(struct orderdata *od, Id *cycle) } } + /* record brkoen cycle starting with the tail */ + queue_push(&od->cycles, od->cyclesdata.count); /* offset into data */ + queue_push(&od->cycles, k / 2); /* cycle elements */ + queue_push(&od->cycles, od->edgedata[cycle[l + 1] + 1]); /* broken edge */ + od->ncycles++; + for (k = l;;) + { + k += 2; + if (!cycle[k + 1]) + k = 0; + queue_push(&od->cyclesdata, cycle[k]); + if (k == l) + break; + } + queue_push(&od->cyclesdata, 0); /* mark end */ + + /* break that edge */ od->edgedata[cycle[l + 1] + 1] |= TYPE_BROKEN; #if 1 @@ -810,9 +901,8 @@ breakcycle(struct orderdata *od, Id *cycle) return; #endif - /* cycle recorded, print it */ - if ((ddegmax & TYPE_PREREQ) != 0) + if (ddegmin >= TYPE_REQ && (ddegmax & TYPE_PREREQ) != 0) printf("CRITICAL "); printf("cycle: --> "); for (k = 0; cycle[k + 1]; k += 2) @@ -826,6 +916,181 @@ breakcycle(struct orderdata *od, Id *cycle) printf("\n"); } +static inline void +dump_tes(struct orderdata *od) +{ + Pool *pool = od->trans->pool; + int i, j; + Queue obsq; + struct _TransactionElement *te, *te2; + + queue_init(&obsq); + for (i = 1, te = od->tes + i; i < od->ntes; i++, te++) + { + Solvable *s = pool->solvables + te->p; + printf("TE %4d: %c%s\n", i, s->repo == pool->installed ? '-' : '+', solvable2str(pool, s)); + if (s->repo != pool->installed) + { + queue_empty(&obsq); + solver_transaction_all_pkgs(od->trans, te->p, &obsq); + for (j = 0; j < obsq.count; j++) + printf(" -%s\n", solvid2str(pool, obsq.elements[j])); + } + for (j = te->edges; od->edgedata[j]; j += 2) + { + te2 = od->tes + od->edgedata[j]; + printf(" --%x--> TE %4d: %s\n", od->edgedata[j + 1], od->edgedata[j], solvid2str(pool, te2->p)); + } + } +} + +#if 1 +static void +reachable(struct orderdata *od, Id i) +{ + struct _TransactionElement *te = od->tes + i; + int j, k; + + if (te->mark != 0) + return; + te->mark = 1; + for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2) + { + if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0) + continue; + if (!od->tes[k].mark) + reachable(od, k); + if (od->tes[k].mark == 2) + { + te->mark = 2; + return; + } + } + te->mark = -1; +} +#endif + +static void +addcycleedges(struct orderdata *od, Id *cycle, Queue *todo) +{ +#if 0 + Transaction *trans = od->trans; + Pool *pool = trans->pool; +#endif + struct _TransactionElement *te; + int i, j, k, tail; +#if 1 + int head; +#endif + +#if 0 + printf("addcycleedges\n"); + for (i = 0; (j = cycle[i]) != 0; i++) + printf("cycle %s\n", solvid2str(pool, od->tes[j].p)); +#endif + + /* first add all the tail cycle edges */ + + /* see what we can reach from the cycle */ + queue_empty(todo); + for (i = 1, te = od->tes + i; i < od->ntes; i++, te++) + te->mark = 0; + for (i = 0; (j = cycle[i]) != 0; i++) + { + od->tes[j].mark = -1; + queue_push(todo, j); + } + while (todo->count) + { + i = queue_pop(todo); + te = od->tes + i; + if (te->mark > 0) + continue; + te->mark = te->mark < 0 ? 2 : 1; + for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2) + { + if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0) + continue; + if (od->tes[k].mark > 0) + continue; /* no need to visit again */ + queue_push(todo, k); + } + } + /* now all cycle TEs are marked with 2, all TEs reachable + * from the cycle are marked with 1 */ + tail = cycle[0]; + od->tes[tail].mark = 1; /* no need to add edges */ + + for (i = 1, te = od->tes + i; i < od->ntes; i++, te++) + { + if (te->mark) + continue; /* reachable from cycle */ + for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2) + { + if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0) + continue; + if (od->tes[k].mark != 2) + continue; + /* We found an edge to the cycle. Add an extra edge to the tail */ + /* the TE was not reachable, so we're not creating a new cycle! */ +#if 0 + printf("adding TO TAIL cycle edge %d->%d %s->%s!\n", i, tail, solvid2str(pool, od->tes[i].p), solvid2str(pool, od->tes[tail].p)); +#endif + j -= te->edges; /* in case we move */ + addteedge(od, i, tail, TYPE_CYCLETAIL); + j += te->edges; + break; /* one edge is enough */ + } + } + +#if 1 + /* now add all head cycle edges */ + + /* reset marks */ + for (i = 1, te = od->tes + i; i < od->ntes; i++, te++) + te->mark = 0; + head = 0; + for (i = 0; (j = cycle[i]) != 0; i++) + { + head = j; + od->tes[j].mark = 2; + } + /* first the head to save some time */ + te = od->tes + head; + for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2) + { + if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0) + continue; + if (!od->tes[k].mark) + reachable(od, k); + if (od->tes[k].mark == -1) + od->tes[k].mark = -2; /* no need for another edge */ + } + for (i = 0; cycle[i] != 0; i++) + { + if (cycle[i] == head) + break; + te = od->tes + cycle[i]; + for (j = te->edges; (k = od->edgedata[j]) != 0; j += 2) + { + if ((od->edgedata[j + 1] & TYPE_BROKEN) != 0) + continue; + /* see if we can reach a cycle TE from k */ + if (!od->tes[k].mark) + reachable(od, k); + if (od->tes[k].mark == -1) + { +#if 0 + printf("adding FROM HEAD cycle edge %d->%d %s->%s [%s]!\n", head, k, solvid2str(pool, od->tes[head].p), solvid2str(pool, od->tes[k].p), solvid2str(pool, od->tes[cycle[i]].p)); +#endif + addteedge(od, head, k, TYPE_CYCLEHEAD); + od->tes[k].mark = -2; /* no need to add that one again */ + } + } + } +#endif +} + void transaction_order(Transaction *trans) { @@ -836,15 +1101,15 @@ transaction_order(Transaction *trans) Solvable *s; int i, j, k, numte, numedge; struct orderdata od; - struct transel *te; + struct _TransactionElement *te; Queue todo, obsq; - int cycstart, cycel, broken; + int cycstart, cycel; Id *cycle, *obstypes; int oldcount; - int now; + int start, now; POOL_DEBUG(SAT_DEBUG_STATS, "ordering transaction\n"); - now = sat_timems(0); + start = now = sat_timems(0); /* create a transaction element for every active component */ numte = 0; for (i = 0; i < tr->count; i += 2) @@ -867,7 +1132,7 @@ transaction_order(Transaction *trans) od.edgedata = sat_extend(0, 0, 1, sizeof(Id), EDGEDATA_BLOCK); od.edgedata[0] = 0; od.nedgedata = 1; - map_init(&od.cycletes, numte); + queue_init(&od.cycles); for (i = 0, te = od.tes + 1; i < tr->count; i += 2) { @@ -877,7 +1142,6 @@ transaction_order(Transaction *trans) continue; te->p = p; te->type = tr->elements[i]; - te->medianr = solvable_lookup_num(s, SOLVABLE_MEDIANR, 0); te++; } @@ -896,10 +1160,13 @@ transaction_order(Transaction *trans) numedge++; POOL_DEBUG(SAT_DEBUG_STATS, "edges: %d, edge space: %d\n", numedge, od.nedgedata / 2); POOL_DEBUG(SAT_DEBUG_STATS, "edge creation took %d ms\n", sat_timems(now)); + +#if 0 + dump_tes(&od); +#endif + now = sat_timems(0); /* kill all cycles */ - broken = 0; - queue_init(&todo); for (i = numte - 1; i > 0; i--) queue_push(&todo, i); @@ -961,8 +1228,8 @@ transaction_order(Transaction *trans) { cycle[k * 2] = cycle[k]; te = od.tes + cycle[k - 1]; - if (te->mark == 1) - te->mark = 0; /* reset investigation marker */ + assert(te->mark == 1); + te->mark = 0; /* reset investigation marker */ /* printf("searching for edge from %d to %d\n", cycle[k - 1], cycle[k]); */ for (j = te->edges; od.edgedata[j]; j += 2) if (od.edgedata[j] == cycle[k]) @@ -973,34 +1240,47 @@ transaction_order(Transaction *trans) /* now cycle looks like this: */ /* te1 edge te2 edge te3 ... teN edge te1 0 */ breakcycle(&od, cycle); - broken++; /* restart with start of cycle */ todo.count = cycstart + 1; } - POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", broken); + POOL_DEBUG(SAT_DEBUG_STATS, "cycles broken: %d\n", od.ncycles); + POOL_DEBUG(SAT_DEBUG_STATS, "cycle breaking took %d ms\n", sat_timems(now)); - /* invert all edges */ - for (i = 1, te = od.tes + i; i < numte; i++, te++) - { - te->invedges = 1; /* term 0 */ - te->mark = 0; /* backref count */ - } + now = sat_timems(0); + /* now go through all broken cycles and create cycle edges to help + the ordering */ + for (i = od.cycles.count - 3; i >= 0; i -= 3) + { + if (od.cycles.elements[i + 2] >= TYPE_REQ) + addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo); + } + for (i = od.cycles.count - 3; i >= 0; i -= 3) + { + if (od.cycles.elements[i + 2] < TYPE_REQ) + addcycleedges(&od, od.cyclesdata.elements + od.cycles.elements[i], &todo); + } + POOL_DEBUG(SAT_DEBUG_STATS, "cycle edge creation took %d ms\n", sat_timems(now)); + /* all edges are finally set up and there are no cycles, now the easy part. + * Create an ordered transaction */ + now = sat_timems(0); + /* first invert all edges */ + for (i = 1, te = od.tes + i; i < numte; i++, te++) + te->mark = 1; /* term 0 */ for (i = 1, te = od.tes + i; i < numte; i++, te++) { for (j = te->edges; od.edgedata[j]; j += 2) { if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0) continue; - struct transel *te2 = od.tes + od.edgedata[j]; - te2->invedges++; + od.tes[od.edgedata[j]].mark++; } } j = 1; for (i = 1, te = od.tes + i; i < numte; i++, te++) { - te->invedges += j; - j = te->invedges; + te->mark += j; + j = te->mark; } POOL_DEBUG(SAT_DEBUG_STATS, "invedge space: %d\n", j + 1); od.invedgedata = sat_calloc(j + 1, sizeof(Id)); @@ -1010,13 +1290,20 @@ transaction_order(Transaction *trans) { if ((od.edgedata[j + 1] & TYPE_BROKEN) != 0) continue; - struct transel *te2 = od.tes + od.edgedata[j]; - od.invedgedata[--te2->invedges] = i; - te->mark++; + od.invedgedata[--od.tes[od.edgedata[j]].mark] = i; } } + for (i = 1, te = od.tes + i; i < numte; i++, te++) + te->edges = te->mark; /* edges now points into invedgedata */ + od.edgedata = sat_free(od.edgedata); + /* now the final ordering */ for (i = 1, te = od.tes + i; i < numte; i++, te++) + te->mark = 0; + for (i = 1, te = od.tes + i; i < numte; i++, te++) + for (j = te->edges; od.invedgedata[j]; j++) + od.tes[od.invedgedata[j]].mark++; + for (i = 1, te = od.tes + i; i < numte; i++, te++) if (te->mark == 0) queue_push(&todo, i); assert(todo.count > 0); @@ -1051,19 +1338,13 @@ transaction_order(Transaction *trans) } } if (i == todo.count) - { - for (i = 0; i < todo.count; i++) - { - j = todo.elements[i]; - if (MAPTST(&od.cycletes, j)) - break; - } - } - if (i == todo.count) - i = 0; + i = 0; te = od.tes + todo.elements[i]; queue_push(tr, te->type); queue_push(tr, te->p); +#if 0 +printf("do %s\n", solvid2str(pool, te->p)); +#endif s = pool->solvables + te->p; if (installed && s->repo != installed) { @@ -1081,24 +1362,187 @@ transaction_order(Transaction *trans) } } } - if (i < todo.count - 1) - memmove(todo.elements + i, todo.elements + i + 1, (todo.count - 1 - i) * sizeof(Id)); - queue_pop(&todo); - for (j = te->invedges; od.invedgedata[j]; j++) + queue_delete(&todo, i); + for (j = te->edges; od.invedgedata[j]; j++) { - struct transel *te2 = od.tes + od.invedgedata[j]; + struct _TransactionElement *te2 = od.tes + od.invedgedata[j]; assert(te2->mark > 0); if (--te2->mark == 0) { queue_push(&todo, od.invedgedata[j]); +#if 0 +printf("free %s\n", solvid2str(pool, od.tes[od.invedgedata[j]].p)); +#endif } } } + sat_free(obstypes); queue_free(&todo); queue_free(&obsq); for (i = 1, te = od.tes + i; i < numte; i++, te++) assert(te->mark == 0); assert(tr->count == oldcount); - POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(now)); + POOL_DEBUG(SAT_DEBUG_STATS, "creating new transaction took %d ms\n", sat_timems(now)); + POOL_DEBUG(SAT_DEBUG_STATS, "transaction ordering took %d ms\n", sat_timems(start)); + + trans->tes = od.tes; + trans->ntes = numte; + trans->invedgedata = od.invedgedata; +} + +static void +transaction_check_pkg(Transaction *trans, Id tepkg, Id pkg, Map *ins, Map *seen, int onlyprereq, Id noconfpkg, int depth) +{ + Pool *pool = trans->pool; + Id p, pp; + Solvable *s; + int good; + + if (MAPTST(seen, pkg)) + return; + MAPSET(seen, pkg); + s = pool->solvables + pkg; +#if 0 + printf("- %*s%c%s\n", depth * 2, "", s->repo == pool->installed ? '-' : '+', solvable2str(pool, s)); +#endif + if (s->requires) + { + Id req, *reqp; + int inpre = 0; + reqp = s->repo->idarraydata + s->requires; + while ((req = *reqp++) != 0) + { + if (req == SOLVABLE_PREREQMARKER) + { + inpre = 1; + continue; + } + if (onlyprereq && !inpre) + continue; + if (!strncmp(id2str(pool, req), "rpmlib(", 7)) + continue; + good = 0; + /* first check kept packages, then freshly installed, then not yet uninstalled */ + FOR_PROVIDES(p, pp, req) + { + if (!MAPTST(ins, p)) + continue; + if (MAPTST(&trans->transactsmap, p)) + continue; + good++; + transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1); + } + if (!good) + { + FOR_PROVIDES(p, pp, req) + { + if (!MAPTST(ins, p)) + continue; + if (pool->solvables[p].repo == pool->installed) + continue; + good++; + transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1); + } + } + if (!good) + { + FOR_PROVIDES(p, pp, req) + { + if (!MAPTST(ins, p)) + continue; + good++; + transaction_check_pkg(trans, tepkg, p, ins, seen, 0, noconfpkg, depth + 1); + } + } + if (!good) + { + printf(" %c%s: nothing provides %s needed by %c%s\n", pool->solvables[tepkg].repo == pool->installed ? '-' : '+', solvid2str(pool, tepkg), dep2str(pool, req), s->repo == pool->installed ? '-' : '+', solvable2str(pool, s)); + } + } + } +} + +void +transaction_check(Transaction *trans) +{ + Pool *pool = trans->pool; + Solvable *s; + Id p, type, lastins; + Map ins, seen; + int i; + + printf("\nchecking transaction order...\n"); + map_init(&ins, pool->nsolvables); + map_init(&seen, pool->nsolvables); + if (pool->installed) + FOR_REPO_SOLVABLES(pool->installed, p, s) + MAPSET(&ins, p); + lastins = 0; + for (i = 0; i < trans->steps.count; i += 2) + { + type = trans->steps.elements[i]; + p = trans->steps.elements[i + 1]; + s = pool->solvables + p; + if (s->repo != pool->installed) + lastins = p; + if (s->repo != pool->installed) + MAPSET(&ins, p); + if (havescripts(pool, p)) + { + MAPZERO(&seen); + transaction_check_pkg(trans, p, p, &ins, &seen, 1, lastins, 0); + } + if (s->repo == pool->installed) + MAPCLR(&ins, p); + } + map_free(&seen); + map_free(&ins); + printf("transaction order check done.\n"); } +int +transaction_add_choices(Transaction *trans, Queue *choices, Id chosen) +{ + int i, j; + struct _TransactionElement *te; + + if (!chosen) + { + /* initialization step */ + for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++) + te->mark = 0; + for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++) + { + for (j = te->edges; trans->invedgedata[j]; j++) + trans->tes[trans->invedgedata[j]].mark++; + } + for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++) + if (!te->mark) + { + queue_push(choices, te->type); + queue_push(choices, te->p); + } + return choices->count; + } + for (i = 1, te = trans->tes + i; i < trans->ntes; i++, te++) + if (te->p == chosen) + break; + if (i == trans->ntes) + return choices->count; + if (te->mark > 0) + { + /* hey! out-of-order installation! */ + te->mark = -1; + } + for (j = te->edges; trans->invedgedata[j]; j++) + { + te = trans->tes + trans->invedgedata[j]; + assert(te->mark > 0 || te->mark == -1); + if (te->mark > 0 && --te->mark == 0) + { + queue_push(choices, te->type); + queue_push(choices, te->p); + } + } + return choices->count; +} diff --git a/src/transaction.h b/src/transaction.h index c1f87b8..ea01d02 100644 --- a/src/transaction.h +++ b/src/transaction.h @@ -23,12 +23,27 @@ extern "C" { struct _Pool; +/* internal */ +struct _TransactionElement { + Id p; /* solvable id */ + Id type; /* installation type */ + Id edges; + Id mark; +}; + typedef struct _Transaction { - struct _Pool *pool; - Queue steps; + struct _Pool *pool; /* back pointer to pool */ + + Queue steps; /* the transaction steps */ + Queue transaction_info; Id *transaction_installed; Map transactsmap; + + struct _TransactionElement *tes; + int ntes; + Id *invedgedata; + } Transaction; @@ -62,6 +77,7 @@ extern void solver_transaction_all_pkgs(Transaction *trans, Id p, Queue *pkgs); extern Id solver_transaction_pkg(Transaction *trans, Id p); extern Id solver_transaction_show(Transaction *trans, Id type, Id p, int mode); extern void transaction_order(Transaction *trans); +extern void transaction_check(Transaction *trans); #ifdef __cplusplus } -- 2.7.4