File: find.c

package info (click to toggle)
hashrat 1.10.2-2
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 1,984 kB
  • sloc: ansic: 21,832; sh: 369; makefile: 187
file content (272 lines) | stat: -rw-r--r-- 5,719 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include "find.h"
#include "files.h"
#include "memcached.h"
#include "fingerprint.h"
#include "check-hash.h"
#include <search.h>


/****************************************************

This file contains the implementation of an in-memory storage/search
system for hashes->paths. It's used in finding duplicate files, files
matching a hash, and changed files.

The libc 'tree' implementation is used for speed, but it can only
store one item per key, so the node items (TFingerprint) have 
a 'next' pointer, so that the system is a tree with linked lists 
hanging off each node.

In 'check' mode items are deleted from this list, so that we can detect
items that have been deleted from the filesystem (as they are still 
left in the tree at the end of a check)

Because the head node is a real data node, and the head of the list
it cannot be deleted if there are other items hanging off it, and so
its path is set to 'blank' instead

****************************************************/



void *Tree=NULL;



int MatchCompareFunc(const void *i1, const void *i2)
{
TFingerprint *M1, *M2;

M1=(TFingerprint *) i1;
M2=(TFingerprint *) i2;


return(strcmp(M1->Hash, M2->Hash));
}


int MatchAdd(TFingerprint *FP, const char *Path, int Flags)
{
TFingerprint *Item;
int result=FALSE;
const char *ptr;
void *vptr;

	if (Flags & FLAG_MEMCACHED)
	{
		ptr=FP->Data;
		if (StrEnd(ptr)) ptr=FP->Path;
		if (StrEnd(ptr)) ptr=Path;
		if (MemcachedSet(FP->Hash, 0, ptr)) result=TRUE;
	}
	else
	{
		vptr=tsearch(FP, &Tree, MatchCompareFunc);
		Item=*(TFingerprint **) vptr;
		if (strcmp(Item->Path, FP->Path) !=0)
		{
			while (Item->Next !=NULL) Item=(TFingerprint *) Item->Next;
			Item->Next=(void *) FP;
		}
		result=TRUE;
	}

	return(result);
}


TFingerprint *FindPathMatches(HashratCtx *Ctx, TFingerprint *Head, const char *Path)
{
TFingerprint *Item=NULL, *Prev=NULL;

Item=Head;
Prev=Head;
while (Item->Next && (strcmp(Path,Item->Path) !=0)) 
{
	Prev=Item;
	Item=Item->Next;
}

if (strcmp(Path, Item->Path)==0) 
{
	if (Ctx->Action==ACT_CHECK) 
	{
		//unclip item from list
		if (Item != Head) Prev->Next=Item->Next;
	}
	return(Item);
}

return(NULL);
}



TFingerprint *CheckForMatch(HashratCtx *Ctx, const char *Path, struct stat *FStat, const char *HashStr)
{
TFingerprint *Lookup, *Head=NULL, *Prev=NULL, *Item=NULL, *Result=NULL;
void *ptr;

if (! StrValid(Path)) return(NULL);

Lookup=TFingerprintCreate(HashStr,"","",Path);
switch (Ctx->Action)
{
	case ACT_FINDMATCHES_MEMCACHED:
	Lookup->Data=MemcachedGet(Lookup->Data, Lookup->Hash);
	if (StrValid(Lookup->Data)) Result=TFingerprintCreate(Lookup->Hash, Lookup->HashType, Lookup->Data, "");
	break;

	case ACT_FINDDUPLICATES:
	case ACT_FINDMATCHES:
	ptr=tfind(Lookup, &Tree, MatchCompareFunc);
	if (ptr)
	{
	Item=*(TFingerprint **) ptr;

	//we have to make a copy because 'Result' is destroyed by parent function
	Result=TFingerprintCreate(Item->Hash, Item->HashType, Item->Data, Item->Path);
	}
	break;

	default:
	ptr=tfind(Lookup, &Tree, MatchCompareFunc);
	if (ptr) 
	{
		Item=FindPathMatches(Ctx, *(TFingerprint **) ptr, Path);
		if (Item) 
		{
		Result=TFingerprintCreate(Item->Hash, Item->HashType, Item->Data, Item->Path);
		if (Ctx->Action==ACT_CHECK)
		{
			if (Item==Head) 
			{
				if (Item->Next==NULL) 
				{
					// tree functions take a copy of the 'head' item, so we cannot
					// destroy it. No idea how they do this, it's magic
					// however we can destroy non-head items that we hang off
					// the tree
					tdelete(Lookup, &Tree, MatchCompareFunc);
				}
				else Item->Path=CopyStr(Item->Path, "");
			}
			//else TFingerprintDestroy(Item);
		}
		}
	}
	break;
}

TFingerprintDestroy(Lookup);

return(Result);
}

void OutputUnmatchedItem(const void *p_Item, const VISIT which, const int depth)
{
	TFingerprint *Item;

	if ((which==preorder) || (which==leaf))
	{
		Item=*(TFingerprint **) p_Item;
	
		while (Item)
		{
			//if a root node of the linked list has been deleted, its path is
			//set blank, rather than actually deleting it, as we need it to 
			//continue acting as the head node
			if (StrValid(Item->Path))
			{
			if (access(Item->Path, F_OK) !=0) HandleCheckFail(Item->Path, "Missing");
			}
			Item=Item->Next;
		}
	}
}


void OutputUnmatched(HashratCtx *Ctx)
{
twalk (Tree, OutputUnmatchedItem);
}


int LoadFromIOC(const char *XML, int Flags)
{
char *TagType=NULL, *TagData=NULL;
const char *ptr;
char *ID=NULL;
int count=0;
TFingerprint *FP;

ptr=XMLGetTag(XML,NULL,&TagType,&TagData);
while (ptr)
{
	if (strcasecmp(TagType,"short_description")==0) ptr=XMLGetTag(ptr,NULL,&TagType,&ID);
	if (
			(strcasecmp(TagType,"content")==0) &&
			(strcasecmp(TagData,"type=\"md5\"")==0)
		)
	{
		ptr=XMLGetTag(ptr,NULL,&TagType,&TagData);
		FP=TFingerprintCreate(TagData, "md5", ID, "");
		if (MatchAdd(FP, ID, Flags)) count++;
	}
	ptr=XMLGetTag(ptr,NULL,&TagType,&TagData);
}

Destroy(ID);
Destroy(TagType);
Destroy(TagData);

return(count);
}




void *MatchesLoad(int Flags)
{
char *Line=NULL, *Tempstr=NULL, *Type=NULL, *ptr;
TFingerprint *FP;
STREAM *S;
int count=0;


S=STREAMFromFD(0);
STREAMSetTimeout(S,100);
Line=STREAMReadLine(Line,S);
if (! StrValid(Line)) return(NULL);

if (strncasecmp(Line,"<?xml ",6)==0) 
{
	//xml document. Must be an OpenIOC fileq
	while (Line)
	{
	StripTrailingWhitespace(Line);
	Tempstr=CatStr(Tempstr,Line);
	Line=STREAMReadLine(Line,S);
	}
	count=LoadFromIOC(Tempstr,Flags);
}
else
{
	while (Line)
	{
	StripTrailingWhitespace(Line);
	FP=TFingerprintParse(Line);
	if (MatchAdd(FP, "", Flags)) count++;
	Line=STREAMReadLine(Line, S);
	}
}

if (Flags & FLAG_MEMCACHED) printf("Stored %d hashes in memcached server\n", count);

Destroy(Tempstr);
Destroy(Line);
Destroy(Type);

return(Tree);
}