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