← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Support/FoldingSet.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Support/FoldingSet.cpp
 
1
//===-- Support/FoldingSet.cpp - Uniquing Hash Set --------------*- C++ -*-===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file implements a hash set that can be used to remove duplication of
 
11
// nodes in a graph.  This code was originally created by Chris Lattner for use
 
12
// with SelectionDAGCSEMap, but was isolated to provide use across the llvm code
 
13
// set. 
 
14
//
 
15
//===----------------------------------------------------------------------===//
 
16
 
 
17
#include "llvm/ADT/FoldingSet.h"
 
18
#include "llvm/Support/Allocator.h"
 
19
#include "llvm/Support/ErrorHandling.h"
 
20
#include "llvm/Support/MathExtras.h"
 
21
#include <cassert>
 
22
#include <cstring>
 
23
using namespace llvm;
 
24
 
 
25
//===----------------------------------------------------------------------===//
 
26
// FoldingSetNodeIDRef Implementation
 
27
 
 
28
/// ComputeHash - Compute a strong hash value for this FoldingSetNodeIDRef,
 
29
/// used to lookup the node in the FoldingSetImpl.
 
30
unsigned FoldingSetNodeIDRef::ComputeHash() const {
 
31
  // This is adapted from SuperFastHash by Paul Hsieh.
 
32
  unsigned Hash = static_cast<unsigned>(Size);
 
33
  for (const unsigned *BP = Data, *E = BP+Size; BP != E; ++BP) {
 
34
    unsigned Data = *BP;
 
35
    Hash         += Data & 0xFFFF;
 
36
    unsigned Tmp  = ((Data >> 16) << 11) ^ Hash;
 
37
    Hash          = (Hash << 16) ^ Tmp;
 
38
    Hash         += Hash >> 11;
 
39
  }
 
40
  
 
41
  // Force "avalanching" of final 127 bits.
 
42
  Hash ^= Hash << 3;
 
43
  Hash += Hash >> 5;
 
44
  Hash ^= Hash << 4;
 
45
  Hash += Hash >> 17;
 
46
  Hash ^= Hash << 25;
 
47
  Hash += Hash >> 6;
 
48
  return Hash;
 
49
}
 
50
 
 
51
bool FoldingSetNodeIDRef::operator==(FoldingSetNodeIDRef RHS) const {
 
52
  if (Size != RHS.Size) return false;
 
53
  return memcmp(Data, RHS.Data, Size*sizeof(*Data)) == 0;
 
54
}
 
55
 
 
56
//===----------------------------------------------------------------------===//
 
57
// FoldingSetNodeID Implementation
 
58
 
 
59
/// Add* - Add various data types to Bit data.
 
60
///
 
61
void FoldingSetNodeID::AddPointer(const void *Ptr) {
 
62
  // Note: this adds pointers to the hash using sizes and endianness that
 
63
  // depend on the host.  It doesn't matter however, because hashing on
 
64
  // pointer values in inherently unstable.  Nothing  should depend on the 
 
65
  // ordering of nodes in the folding set.
 
66
  intptr_t PtrI = (intptr_t)Ptr;
 
67
  Bits.push_back(unsigned(PtrI));
 
68
  if (sizeof(intptr_t) > sizeof(unsigned))
 
69
    Bits.push_back(unsigned(uint64_t(PtrI) >> 32));
 
70
}
 
71
void FoldingSetNodeID::AddInteger(signed I) {
 
72
  Bits.push_back(I);
 
73
}
 
74
void FoldingSetNodeID::AddInteger(unsigned I) {
 
75
  Bits.push_back(I);
 
76
}
 
77
void FoldingSetNodeID::AddInteger(long I) {
 
78
  AddInteger((unsigned long)I);
 
79
}
 
80
void FoldingSetNodeID::AddInteger(unsigned long I) {
 
81
  if (sizeof(long) == sizeof(int))
 
82
    AddInteger(unsigned(I));
 
83
  else if (sizeof(long) == sizeof(long long)) {
 
84
    AddInteger((unsigned long long)I);
 
85
  } else {
 
86
    llvm_unreachable("unexpected sizeof(long)");
 
87
  }
 
88
}
 
89
void FoldingSetNodeID::AddInteger(long long I) {
 
90
  AddInteger((unsigned long long)I);
 
91
}
 
92
void FoldingSetNodeID::AddInteger(unsigned long long I) {
 
93
  AddInteger(unsigned(I));
 
94
  if ((uint64_t)(int)I != I)
 
95
    Bits.push_back(unsigned(I >> 32));
 
96
}
 
97
 
 
98
void FoldingSetNodeID::AddString(StringRef String) {
 
99
  unsigned Size =  String.size();
 
100
  Bits.push_back(Size);
 
101
  if (!Size) return;
 
102
 
 
103
  unsigned Units = Size / 4;
 
104
  unsigned Pos = 0;
 
105
  const unsigned *Base = (const unsigned*) String.data();
 
106
  
 
107
  // If the string is aligned do a bulk transfer.
 
108
  if (!((intptr_t)Base & 3)) {
 
109
    Bits.append(Base, Base + Units);
 
110
    Pos = (Units + 1) * 4;
 
111
  } else {
 
112
    // Otherwise do it the hard way.
 
113
    for (Pos += 4; Pos <= Size; Pos += 4) {
 
114
      unsigned V = ((unsigned char)String[Pos - 4] << 24) |
 
115
                   ((unsigned char)String[Pos - 3] << 16) |
 
116
                   ((unsigned char)String[Pos - 2] << 8) |
 
117
                    (unsigned char)String[Pos - 1];
 
118
      Bits.push_back(V);
 
119
    }
 
120
  }
 
121
  
 
122
  // With the leftover bits.
 
123
  unsigned V = 0;
 
124
  // Pos will have overshot size by 4 - #bytes left over. 
 
125
  switch (Pos - Size) {
 
126
  case 1: V = (V << 8) | (unsigned char)String[Size - 3]; // Fall thru.
 
127
  case 2: V = (V << 8) | (unsigned char)String[Size - 2]; // Fall thru.
 
128
  case 3: V = (V << 8) | (unsigned char)String[Size - 1]; break;
 
129
  default: return; // Nothing left.
 
130
  }
 
131
 
 
132
  Bits.push_back(V);
 
133
}
 
134
 
 
135
/// ComputeHash - Compute a strong hash value for this FoldingSetNodeID, used to 
 
136
/// lookup the node in the FoldingSetImpl.
 
137
unsigned FoldingSetNodeID::ComputeHash() const {
 
138
  return FoldingSetNodeIDRef(Bits.data(), Bits.size()).ComputeHash();
 
139
}
 
140
 
 
141
/// operator== - Used to compare two nodes to each other.
 
142
///
 
143
bool FoldingSetNodeID::operator==(const FoldingSetNodeID &RHS)const{
 
144
  return *this == FoldingSetNodeIDRef(RHS.Bits.data(), RHS.Bits.size());
 
145
}
 
146
 
 
147
/// operator== - Used to compare two nodes to each other.
 
148
///
 
149
bool FoldingSetNodeID::operator==(FoldingSetNodeIDRef RHS) const {
 
150
  return FoldingSetNodeIDRef(Bits.data(), Bits.size()) == RHS;
 
151
}
 
152
 
 
153
/// Intern - Copy this node's data to a memory region allocated from the
 
154
/// given allocator and return a FoldingSetNodeIDRef describing the
 
155
/// interned data.
 
156
FoldingSetNodeIDRef
 
157
FoldingSetNodeID::Intern(BumpPtrAllocator &Allocator) const {
 
158
  unsigned *New = Allocator.Allocate<unsigned>(Bits.size());
 
159
  std::uninitialized_copy(Bits.begin(), Bits.end(), New);
 
160
  return FoldingSetNodeIDRef(New, Bits.size());
 
161
}
 
162
 
 
163
//===----------------------------------------------------------------------===//
 
164
/// Helper functions for FoldingSetImpl.
 
165
 
 
166
/// GetNextPtr - In order to save space, each bucket is a
 
167
/// singly-linked-list. In order to make deletion more efficient, we make
 
168
/// the list circular, so we can delete a node without computing its hash.
 
169
/// The problem with this is that the start of the hash buckets are not
 
170
/// Nodes.  If NextInBucketPtr is a bucket pointer, this method returns null:
 
171
/// use GetBucketPtr when this happens.
 
172
static FoldingSetImpl::Node *GetNextPtr(void *NextInBucketPtr) {
 
173
  // The low bit is set if this is the pointer back to the bucket.
 
174
  if (reinterpret_cast<intptr_t>(NextInBucketPtr) & 1)
 
175
    return 0;
 
176
  
 
177
  return static_cast<FoldingSetImpl::Node*>(NextInBucketPtr);
 
178
}
 
179
 
 
180
 
 
181
/// testing.
 
182
static void **GetBucketPtr(void *NextInBucketPtr) {
 
183
  intptr_t Ptr = reinterpret_cast<intptr_t>(NextInBucketPtr);
 
184
  assert((Ptr & 1) && "Not a bucket pointer");
 
185
  return reinterpret_cast<void**>(Ptr & ~intptr_t(1));
 
186
}
 
187
 
 
188
/// GetBucketFor - Hash the specified node ID and return the hash bucket for
 
189
/// the specified ID.
 
190
static void **GetBucketFor(unsigned Hash, void **Buckets, unsigned NumBuckets) {
 
191
  // NumBuckets is always a power of 2.
 
192
  unsigned BucketNum = Hash & (NumBuckets-1);
 
193
  return Buckets + BucketNum;
 
194
}
 
195
 
 
196
/// AllocateBuckets - Allocated initialized bucket memory.
 
197
static void **AllocateBuckets(unsigned NumBuckets) {
 
198
  void **Buckets = static_cast<void**>(calloc(NumBuckets+1, sizeof(void*)));
 
199
  // Set the very last bucket to be a non-null "pointer".
 
200
  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
 
201
  return Buckets;
 
202
}
 
203
 
 
204
//===----------------------------------------------------------------------===//
 
205
// FoldingSetImpl Implementation
 
206
 
 
207
FoldingSetImpl::FoldingSetImpl(unsigned Log2InitSize) {
 
208
  assert(5 < Log2InitSize && Log2InitSize < 32 &&
 
209
         "Initial hash table size out of range");
 
210
  NumBuckets = 1 << Log2InitSize;
 
211
  Buckets = AllocateBuckets(NumBuckets);
 
212
  NumNodes = 0;
 
213
}
 
214
FoldingSetImpl::~FoldingSetImpl() {
 
215
  free(Buckets);
 
216
}
 
217
void FoldingSetImpl::clear() {
 
218
  // Set all but the last bucket to null pointers.
 
219
  memset(Buckets, 0, NumBuckets*sizeof(void*));
 
220
 
 
221
  // Set the very last bucket to be a non-null "pointer".
 
222
  Buckets[NumBuckets] = reinterpret_cast<void*>(-1);
 
223
 
 
224
  // Reset the node count to zero.
 
225
  NumNodes = 0;
 
226
}
 
227
 
 
228
/// GrowHashTable - Double the size of the hash table and rehash everything.
 
229
///
 
230
void FoldingSetImpl::GrowHashTable() {
 
231
  void **OldBuckets = Buckets;
 
232
  unsigned OldNumBuckets = NumBuckets;
 
233
  NumBuckets <<= 1;
 
234
  
 
235
  // Clear out new buckets.
 
236
  Buckets = AllocateBuckets(NumBuckets);
 
237
  NumNodes = 0;
 
238
 
 
239
  // Walk the old buckets, rehashing nodes into their new place.
 
240
  FoldingSetNodeID TempID;
 
241
  for (unsigned i = 0; i != OldNumBuckets; ++i) {
 
242
    void *Probe = OldBuckets[i];
 
243
    if (!Probe) continue;
 
244
    while (Node *NodeInBucket = GetNextPtr(Probe)) {
 
245
      // Figure out the next link, remove NodeInBucket from the old link.
 
246
      Probe = NodeInBucket->getNextInBucket();
 
247
      NodeInBucket->SetNextInBucket(0);
 
248
 
 
249
      // Insert the node into the new bucket, after recomputing the hash.
 
250
      InsertNode(NodeInBucket,
 
251
                 GetBucketFor(ComputeNodeHash(NodeInBucket, TempID),
 
252
                              Buckets, NumBuckets));
 
253
      TempID.clear();
 
254
    }
 
255
  }
 
256
  
 
257
  free(OldBuckets);
 
258
}
 
259
 
 
260
/// FindNodeOrInsertPos - Look up the node specified by ID.  If it exists,
 
261
/// return it.  If not, return the insertion token that will make insertion
 
262
/// faster.
 
263
FoldingSetImpl::Node
 
264
*FoldingSetImpl::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
 
265
                                     void *&InsertPos) {
 
266
  
 
267
  void **Bucket = GetBucketFor(ID.ComputeHash(), Buckets, NumBuckets);
 
268
  void *Probe = *Bucket;
 
269
  
 
270
  InsertPos = 0;
 
271
  
 
272
  FoldingSetNodeID TempID;
 
273
  while (Node *NodeInBucket = GetNextPtr(Probe)) {
 
274
    if (NodeEquals(NodeInBucket, ID, TempID))
 
275
      return NodeInBucket;
 
276
    TempID.clear();
 
277
 
 
278
    Probe = NodeInBucket->getNextInBucket();
 
279
  }
 
280
  
 
281
  // Didn't find the node, return null with the bucket as the InsertPos.
 
282
  InsertPos = Bucket;
 
283
  return 0;
 
284
}
 
285
 
 
286
/// InsertNode - Insert the specified node into the folding set, knowing that it
 
287
/// is not already in the map.  InsertPos must be obtained from 
 
288
/// FindNodeOrInsertPos.
 
289
void FoldingSetImpl::InsertNode(Node *N, void *InsertPos) {
 
290
  assert(N->getNextInBucket() == 0);
 
291
  // Do we need to grow the hashtable?
 
292
  if (NumNodes+1 > NumBuckets*2) {
 
293
    GrowHashTable();
 
294
    FoldingSetNodeID TempID;
 
295
    InsertPos = GetBucketFor(ComputeNodeHash(N, TempID), Buckets, NumBuckets);
 
296
  }
 
297
 
 
298
  ++NumNodes;
 
299
  
 
300
  /// The insert position is actually a bucket pointer.
 
301
  void **Bucket = static_cast<void**>(InsertPos);
 
302
  
 
303
  void *Next = *Bucket;
 
304
  
 
305
  // If this is the first insertion into this bucket, its next pointer will be
 
306
  // null.  Pretend as if it pointed to itself, setting the low bit to indicate
 
307
  // that it is a pointer to the bucket.
 
308
  if (Next == 0)
 
309
    Next = reinterpret_cast<void*>(reinterpret_cast<intptr_t>(Bucket)|1);
 
310
 
 
311
  // Set the node's next pointer, and make the bucket point to the node.
 
312
  N->SetNextInBucket(Next);
 
313
  *Bucket = N;
 
314
}
 
315
 
 
316
/// RemoveNode - Remove a node from the folding set, returning true if one was
 
317
/// removed or false if the node was not in the folding set.
 
318
bool FoldingSetImpl::RemoveNode(Node *N) {
 
319
  // Because each bucket is a circular list, we don't need to compute N's hash
 
320
  // to remove it.
 
321
  void *Ptr = N->getNextInBucket();
 
322
  if (Ptr == 0) return false;  // Not in folding set.
 
323
 
 
324
  --NumNodes;
 
325
  N->SetNextInBucket(0);
 
326
 
 
327
  // Remember what N originally pointed to, either a bucket or another node.
 
328
  void *NodeNextPtr = Ptr;
 
329
  
 
330
  // Chase around the list until we find the node (or bucket) which points to N.
 
331
  while (true) {
 
332
    if (Node *NodeInBucket = GetNextPtr(Ptr)) {
 
333
      // Advance pointer.
 
334
      Ptr = NodeInBucket->getNextInBucket();
 
335
      
 
336
      // We found a node that points to N, change it to point to N's next node,
 
337
      // removing N from the list.
 
338
      if (Ptr == N) {
 
339
        NodeInBucket->SetNextInBucket(NodeNextPtr);
 
340
        return true;
 
341
      }
 
342
    } else {
 
343
      void **Bucket = GetBucketPtr(Ptr);
 
344
      Ptr = *Bucket;
 
345
      
 
346
      // If we found that the bucket points to N, update the bucket to point to
 
347
      // whatever is next.
 
348
      if (Ptr == N) {
 
349
        *Bucket = NodeNextPtr;
 
350
        return true;
 
351
      }
 
352
    }
 
353
  }
 
354
}
 
355
 
 
356
/// GetOrInsertNode - If there is an existing simple Node exactly
 
357
/// equal to the specified node, return it.  Otherwise, insert 'N' and it
 
358
/// instead.
 
359
FoldingSetImpl::Node *FoldingSetImpl::GetOrInsertNode(FoldingSetImpl::Node *N) {
 
360
  FoldingSetNodeID ID;
 
361
  GetNodeProfile(N, ID);
 
362
  void *IP;
 
363
  if (Node *E = FindNodeOrInsertPos(ID, IP))
 
364
    return E;
 
365
  InsertNode(N, IP);
 
366
  return N;
 
367
}
 
368
 
 
369
//===----------------------------------------------------------------------===//
 
370
// FoldingSetIteratorImpl Implementation
 
371
 
 
372
FoldingSetIteratorImpl::FoldingSetIteratorImpl(void **Bucket) {
 
373
  // Skip to the first non-null non-self-cycle bucket.
 
374
  while (*Bucket != reinterpret_cast<void*>(-1) &&
 
375
         (*Bucket == 0 || GetNextPtr(*Bucket) == 0))
 
376
    ++Bucket;
 
377
  
 
378
  NodePtr = static_cast<FoldingSetNode*>(*Bucket);
 
379
}
 
380
 
 
381
void FoldingSetIteratorImpl::advance() {
 
382
  // If there is another link within this bucket, go to it.
 
383
  void *Probe = NodePtr->getNextInBucket();
 
384
 
 
385
  if (FoldingSetNode *NextNodeInBucket = GetNextPtr(Probe))
 
386
    NodePtr = NextNodeInBucket;
 
387
  else {
 
388
    // Otherwise, this is the last link in this bucket.  
 
389
    void **Bucket = GetBucketPtr(Probe);
 
390
 
 
391
    // Skip to the next non-null non-self-cycle bucket.
 
392
    do {
 
393
      ++Bucket;
 
394
    } while (*Bucket != reinterpret_cast<void*>(-1) &&
 
395
             (*Bucket == 0 || GetNextPtr(*Bucket) == 0));
 
396
    
 
397
    NodePtr = static_cast<FoldingSetNode*>(*Bucket);
 
398
  }
 
399
}
 
400
 
 
401
//===----------------------------------------------------------------------===//
 
402
// FoldingSetBucketIteratorImpl Implementation
 
403
 
 
404
FoldingSetBucketIteratorImpl::FoldingSetBucketIteratorImpl(void **Bucket) {
 
405
  Ptr = (*Bucket == 0 || GetNextPtr(*Bucket) == 0) ? (void*) Bucket : *Bucket;
 
406
}