- rename all sat_ to solv_
[platform/upstream/libsolv.git] / ext / pool_fileconflicts.c
1 #include <stdio.h>
2 #include <sys/stat.h>
3
4 #include "pool.h"
5 #include "repo.h"
6 #include "hash.h"
7 #include "repo_rpmdb.h"
8 #include "pool_fileconflicts.h"
9
10 struct cbdata {
11   Pool *pool;
12   int create;
13
14   Queue lookat;
15   Queue lookat_dir;
16
17   Hashval *cflmap;
18   Hashmask cflmapn;
19   unsigned int cflmapused;
20
21   Hashval *dirmap;
22   Hashmask dirmapn;
23   unsigned int dirmapused;
24   int dirconflicts;
25
26   Map idxmap;
27
28   Hashval idx;
29   unsigned int hx;
30
31   Queue files;
32   unsigned char *filesspace;
33   unsigned int filesspacen;
34 };
35
36 #define FILESSPACE_BLOCK 255
37
38 static Hashval *
39 doublehash(Hashval *map, Hashmask *mapnp)
40 {
41   Hashmask mapn = *mapnp;
42   Hashmask i, hx, qx, h, hh;
43   Hashmask nn = (mapn + 1) * 2 - 1;
44   Hashmask *m;
45
46   m = solv_calloc(nn + 1, 2 * sizeof(Id));
47   for (i = 0; i <= mapn; i++)
48     {
49       hx = map[2 * i];
50       if (!hx)
51         continue;
52       h = hx & nn;
53       hh = HASHCHAIN_START;
54       for (;;)
55         {
56           qx = m[2 * h];
57           if (!qx)
58             break;
59           h = HASHCHAIN_NEXT(h, hh, nn);
60         }
61       m[2 * h] = hx;
62       m[2 * h + 1] = map[2 * i + 1];
63     }
64   solv_free(map);
65   *mapnp = nn;
66   return m;
67 }
68
69 static void
70 finddirs_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
71 {
72   struct cbdata *cbdata = cbdatav;
73   Hashmask h, hh, hx, qx;
74   Hashval idx = cbdata->idx;
75
76   hx = strhash(fn);
77   if (!hx)
78     hx = strlen(fn) + 1;
79   h = hx & cbdata->dirmapn;
80   hh = HASHCHAIN_START;
81   for (;;)
82     {
83       qx = cbdata->dirmap[2 * h];
84       if (!qx)
85         break;
86       if (qx == hx)
87         break;
88       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
89     }
90   if (!qx)
91     {
92       /* a miss */
93       if (!cbdata->create)
94         return;
95       cbdata->dirmap[2 * h] = hx;
96       cbdata->dirmap[2 * h + 1] = idx;
97       cbdata->dirmapused++;
98       if (cbdata->dirmapused * 2 > cbdata->dirmapn)
99         cbdata->dirmap = doublehash(cbdata->dirmap, &cbdata->dirmapn);
100       return;
101     }
102   if (cbdata->dirmap[2 * h + 1] == idx)
103     return;
104   /* found a conflict, this dir is used in multiple packages */
105   if (cbdata->dirmap[2 * h + 1] != -1)
106     {
107       MAPSET(&cbdata->idxmap, cbdata->dirmap[2 * h + 1]);
108       cbdata->dirmap[2 * h + 1] = -1;
109       cbdata->dirconflicts++;
110     }
111   MAPSET(&cbdata->idxmap, idx);
112 }
113
114 static inline int
115 isindirmap(struct cbdata *cbdata, Hashmask hx)
116 {
117   Hashmask h, hh, qx;
118
119   h = hx & cbdata->dirmapn;
120   hh = HASHCHAIN_START;
121   for (;;)
122     {
123       qx = cbdata->dirmap[2 * h];
124       if (!qx)
125         return 0;
126       if (qx == hx)
127         return cbdata->dirmap[2 * h + 1] == -1 ? 1 : 0;
128       h = HASHCHAIN_NEXT(h, hh, cbdata->dirmapn);
129     }
130 }
131
132 static void
133 findfileconflicts_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
134 {
135   struct cbdata *cbdata = cbdatav;
136   int isdir = S_ISDIR(fmode);
137   char *dp;
138   Hashval idx, qidx;
139   Hashmask qx, h, hx, hh, dhx;
140
141   idx = cbdata->idx;
142
143   dp = strrchr(fn, '/');
144   if (!dp)
145     return;
146   dhx = strnhash(fn, dp + 1 - fn);
147   if (!dhx)
148     dhx = 1 + dp + 1 - fn;
149 #if 1
150   if (!isindirmap(cbdata, dhx))
151     return;
152 #endif
153
154   hx = strhash_cont(dp + 1, dhx);
155   if (!hx)
156     hx = strlen(fn) + 1;
157
158   h = hx & cbdata->cflmapn;
159   hh = HASHCHAIN_START;
160   for (;;)
161     {
162       qx = cbdata->cflmap[2 * h];
163       if (!qx)
164         break;
165       if (qx == hx)
166         break;
167       h = HASHCHAIN_NEXT(h, hh, cbdata->cflmapn);
168     }
169   if (!qx)
170     {
171       /* a miss */
172       if (!cbdata->create)
173         return;
174       cbdata->cflmap[2 * h] = hx;
175       cbdata->cflmap[2 * h + 1] = (isdir ? ~idx : idx);
176       cbdata->cflmapused++;
177       if (cbdata->cflmapused * 2 > cbdata->cflmapn)
178         cbdata->cflmap = doublehash(cbdata->cflmap, &cbdata->cflmapn);
179       return;
180     }
181   qidx = cbdata->cflmap[2 * h + 1];
182   if ((int)qidx < 0)
183     {
184       int i;
185       qidx = ~qidx;
186       if (isdir)
187         {
188           /* delay the conflict */
189           queue_push2(&cbdata->lookat_dir, hx, qidx);
190           queue_push2(&cbdata->lookat_dir, hx, idx);
191           return;
192         }
193       cbdata->cflmap[2 * h + 1] = qidx;
194       for (i = 0; i < cbdata->lookat_dir.count; i += 2)
195         if (cbdata->lookat_dir.elements[i] == hx)
196           queue_push2(&cbdata->lookat, hx, cbdata->lookat_dir.elements[i + 1]);
197     }
198   if (qidx == idx)
199     return;     /* no conflicts with ourself, please */
200   queue_push2(&cbdata->lookat, hx, qidx);
201   queue_push2(&cbdata->lookat, hx, idx);
202 }
203
204 static inline void
205 addfilesspace(struct cbdata *cbdata, unsigned char *data, int len)
206 {
207   cbdata->filesspace = solv_extend(cbdata->filesspace, cbdata->filesspacen, len, 1, FILESSPACE_BLOCK);
208   memcpy(cbdata->filesspace + cbdata->filesspacen, data, len);
209   cbdata->filesspacen += len;
210 }
211
212 static void
213 findfileconflicts2_cb(void *cbdatav, const char *fn, int fmode, const char *md5)
214 {
215   struct cbdata *cbdata = cbdatav;
216   unsigned int hx = strhash(fn);
217   char md5padded[34];
218
219   if (!hx)
220     hx = strlen(fn) + 1;
221   if (hx != cbdata->hx)
222     return;
223   strncpy(md5padded, md5, 32);
224   md5padded[32] = 0;
225   md5padded[33] = fmode >> 24;
226   // printf("%d, hx %x -> %s   %d %s\n", cbdata->idx, hx, fn, fmode, md5);
227   queue_push(&cbdata->files, cbdata->filesspacen);
228   addfilesspace(cbdata, (unsigned char *)md5padded, 34);
229   addfilesspace(cbdata, (unsigned char *)fn, strlen(fn) + 1);
230 }
231
232 static int cand_sort(const void *ap, const void *bp, void *dp)
233 {
234   const Id *a = ap;
235   const Id *b = bp;
236
237   unsigned int ax = (unsigned int)a[0];
238   unsigned int bx = (unsigned int)b[0];
239   if (ax < bx)
240     return -1;
241   if (ax > bx)
242     return 1;
243   return (a[1] < 0 ? -a[1] : a[1]) - (b[1] < 0 ? -b[1] : b[1]);
244 }
245
246 static int conflicts_cmp(const void *ap, const void *bp, void *dp)
247 {
248   Pool *pool = dp;
249   const Id *a = ap;
250   const Id *b = bp;
251   if (a[0] != b[0])
252     return strcmp(pool_id2str(pool, a[0]), pool_id2str(pool, b[0]));
253   if (a[1] != b[1])
254     return a[1] - b[1];
255   if (a[3] != b[3])
256     return a[3] - b[3];
257   return 0;
258 }
259
260 int
261 pool_findfileconflicts(Pool *pool, Queue *pkgs, int cutoff, Queue *conflicts, void *(*handle_cb)(Pool *, Id, void *) , void *handle_cbdata)
262 {
263   int i, j, cflmapn, idxmapset;
264   unsigned int hx;
265   struct cbdata cbdata;
266   unsigned int now, start;
267   void *handle;
268   Id p;
269
270   queue_empty(conflicts);
271   if (!pkgs->count)
272     return 0;
273
274   now = start = solv_timems(0);
275   POOL_DEBUG(SOLV_DEBUG_STATS, "searching for file conflicts\n");
276   POOL_DEBUG(SOLV_DEBUG_STATS, "packages: %d, cutoff %d\n", pkgs->count, cutoff);
277
278   memset(&cbdata, 0, sizeof(cbdata));
279   cbdata.pool = pool;
280   queue_init(&cbdata.lookat);
281   queue_init(&cbdata.lookat_dir);
282   queue_init(&cbdata.files);
283   map_init(&cbdata.idxmap, pkgs->count);
284
285   if (cutoff <= 0)
286     cutoff = pkgs->count;
287
288   /* avarage file list size: 200 files per package */
289   /* avarage dir count: 20 dirs per package */
290
291   /* first pass: scan dirs */
292   cflmapn = (cutoff + 3) * 64;
293   while ((cflmapn & (cflmapn - 1)) != 0)
294     cflmapn = cflmapn & (cflmapn - 1);
295   cbdata.dirmap = solv_calloc(cflmapn, 2 * sizeof(Id));
296   cbdata.dirmapn = cflmapn - 1; /* make it a mask */
297   cbdata.create = 1;
298   idxmapset = 0;
299   for (i = 0; i < pkgs->count; i++)
300     {
301       p = pkgs->elements[i];
302       cbdata.idx = i;
303       if (i == cutoff)
304         cbdata.create = 0;
305       handle = (*handle_cb)(pool, p, handle_cbdata);
306       if (handle)
307         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_ONLYDIRS, finddirs_cb, &cbdata);
308       if (MAPTST(&cbdata.idxmap, i))
309         idxmapset++;
310     }
311
312   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap size: %d used %d\n", cbdata.dirmapn + 1, cbdata.dirmapused);
313   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap memory usage: %d K\n", (cbdata.dirmapn + 1) * 2 * (int)sizeof(Id) / 1024);
314   POOL_DEBUG(SOLV_DEBUG_STATS, "dirmap creation took %d ms\n", solv_timems(now));
315   POOL_DEBUG(SOLV_DEBUG_STATS, "dir conflicts found: %d, idxmap %d of %d\n", cbdata.dirconflicts, idxmapset, pkgs->count);
316
317   /* second pass: scan files */
318   now = solv_timems(0);
319   cflmapn = (cutoff + 3) * 128;
320   while ((cflmapn & (cflmapn - 1)) != 0)
321     cflmapn = cflmapn & (cflmapn - 1);
322   cbdata.cflmap = solv_calloc(cflmapn, 2 * sizeof(Id));
323   cbdata.cflmapn = cflmapn - 1; /* make it a mask */
324   cbdata.create = 1;
325   for (i = 0; i < pkgs->count; i++)
326     {
327       if (!MAPTST(&cbdata.idxmap, i))
328         continue;
329       p = pkgs->elements[i];
330       cbdata.idx = i;
331       if (i == cutoff)
332         cbdata.create = 0;
333       handle = (*handle_cb)(pool, p, handle_cbdata);
334       if (handle)
335         rpm_iterate_filelist(handle, RPM_ITERATE_FILELIST_NOGHOSTS, findfileconflicts_cb, &cbdata);
336     }
337
338   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap size: %d used %d\n", cbdata.cflmapn + 1, cbdata.cflmapused);
339   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap memory usage: %d K\n", (cbdata.cflmapn + 1) * 2 * (int)sizeof(Id) / 1024);
340   POOL_DEBUG(SOLV_DEBUG_STATS, "filemap creation took %d ms\n", solv_timems(now));
341
342   cbdata.dirmap = solv_free(cbdata.dirmap);
343   cbdata.dirmapn = 0;
344   cbdata.dirmapused = 0;
345   cbdata.cflmap = solv_free(cbdata.cflmap);
346   cbdata.cflmapn = 0;
347   cbdata.cflmapused = 0;
348   map_free(&cbdata.idxmap);
349
350   now = solv_timems(0);
351   POOL_DEBUG(SOLV_DEBUG_STATS, "lookat_dir size: %d\n", cbdata.lookat_dir.count);
352   queue_free(&cbdata.lookat_dir);
353   solv_sort(cbdata.lookat.elements, cbdata.lookat.count / 2, sizeof(Id) * 2, &cand_sort, pool);
354   /* unify */
355   for (i = j = 0; i < cbdata.lookat.count; i += 2)
356     {
357       hx = cbdata.lookat.elements[i];
358       Id idx = cbdata.lookat.elements[i + 1];
359       if (j && hx == cbdata.lookat.elements[j - 2] && idx == cbdata.lookat.elements[j - 1])
360         continue;
361       cbdata.lookat.elements[j++] = hx;
362       cbdata.lookat.elements[j++] = idx;
363     }
364   POOL_DEBUG(SOLV_DEBUG_STATS, "candidates: %d\n", cbdata.lookat.count / 2);
365
366   /* third pass: scan candidates */
367   for (i = 0; i < cbdata.lookat.count - 2; i += 2)
368     {
369       int pend, ii, jj;
370       int pidx = cbdata.lookat.elements[i + 1];
371       int iterflags;
372
373       iterflags = RPM_ITERATE_FILELIST_WITHMD5 | RPM_ITERATE_FILELIST_NOGHOSTS;
374       if (pool->obsoleteusescolors)
375         iterflags |= RPM_ITERATE_FILELIST_WITHCOL;
376       p = pkgs->elements[pidx];
377       hx = cbdata.lookat.elements[i];
378       if (cbdata.lookat.elements[i + 2] != hx)
379         continue;       /* no package left */
380       queue_empty(&cbdata.files);
381       cbdata.filesspace = solv_free(cbdata.filesspace);
382       cbdata.filesspacen = 0;
383
384       cbdata.idx = p;
385       cbdata.hx = cbdata.lookat.elements[i];
386       handle = (*handle_cb)(pool, p, handle_cbdata);
387       if (!handle)
388         continue;
389       rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
390
391       pend = cbdata.files.count;
392       for (j = i + 2; j < cbdata.lookat.count && cbdata.lookat.elements[j] == hx; j++)
393         {
394           int qidx = cbdata.lookat.elements[j + 1];
395           Id q = pkgs->elements[qidx];
396           if (pidx >= cutoff && qidx >= cutoff)
397             continue;   /* no conflicts between packages with idx >= cutoff */
398           cbdata.idx = q;
399           handle = (*handle_cb)(pool, q, handle_cbdata);
400           if (!handle)
401             continue;
402           rpm_iterate_filelist(handle, iterflags, findfileconflicts2_cb, &cbdata);
403           for (ii = 0; ii < pend; ii++)
404             for (jj = pend; jj < cbdata.files.count; jj++)
405               {
406                 char *fsi = (char *)cbdata.filesspace + cbdata.files.elements[ii];
407                 char *fsj = (char *)cbdata.filesspace + cbdata.files.elements[jj];
408                 if (strcmp(fsi + 34, fsj + 34))
409                   continue;     /* different file names */
410                 if (!strcmp(fsi, fsj))
411                   continue;     /* md5 sum matches */
412                 if (pool->obsoleteusescolors && fsi[33] && fsj[33] && (fsi[33] & fsj[33]) == 0)
413                   continue;     /* colors do not conflict */
414                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii] + 34, 1));
415                 queue_push(conflicts, p);
416                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[ii], 1));
417                 queue_push(conflicts, q);
418                 queue_push(conflicts, pool_str2id(pool, (char *)cbdata.filesspace + cbdata.files.elements[jj], 1));
419               }
420         }
421     }
422   cbdata.filesspace = solv_free(cbdata.filesspace);
423   cbdata.filesspacen = 0;
424   queue_free(&cbdata.lookat);
425   queue_free(&cbdata.files);
426   POOL_DEBUG(SOLV_DEBUG_STATS, "candidate check took %d ms\n", solv_timems(now));
427   if (conflicts->count > 5)
428     solv_sort(conflicts->elements, conflicts->count / 5, 5 * sizeof(Id), conflicts_cmp, pool);
429   (*handle_cb)(pool, 0, handle_cbdata);
430   POOL_DEBUG(SOLV_DEBUG_STATS, "found %d file conflicts\n", conflicts->count / 5);
431   POOL_DEBUG(SOLV_DEBUG_STATS, "file conflict detection took %d ms\n", solv_timems(start));
432   return conflicts->count;
433 }
434