]>
Commit | Line | Data |
---|---|---|
42cc7485 JT |
1 | #include "cache.h" |
2 | #include "skipping.h" | |
3 | #include "../commit.h" | |
4 | #include "../fetch-negotiator.h" | |
5 | #include "../prio-queue.h" | |
6 | #include "../refs.h" | |
7 | #include "../tag.h" | |
8 | ||
9 | /* Remember to update object flag allocation in object.h */ | |
10 | /* | |
11 | * Both us and the server know that both parties have this object. | |
12 | */ | |
13 | #define COMMON (1U << 2) | |
14 | /* | |
15 | * The server has told us that it has this object. We still need to tell the | |
16 | * server that we have this object (or one of its descendants), but since we are | |
17 | * going to do that, we do not need to tell the server about its ancestors. | |
18 | */ | |
19 | #define ADVERTISED (1U << 3) | |
20 | /* | |
21 | * This commit has entered the priority queue. | |
22 | */ | |
23 | #define SEEN (1U << 4) | |
24 | /* | |
25 | * This commit has left the priority queue. | |
26 | */ | |
27 | #define POPPED (1U << 5) | |
28 | ||
29 | static int marked; | |
30 | ||
31 | /* | |
32 | * An entry in the priority queue. | |
33 | */ | |
34 | struct entry { | |
35 | struct commit *commit; | |
36 | ||
37 | /* | |
38 | * Used only if commit is not COMMON. | |
39 | */ | |
40 | uint16_t original_ttl; | |
41 | uint16_t ttl; | |
42 | }; | |
43 | ||
44 | struct data { | |
45 | struct prio_queue rev_list; | |
46 | ||
47 | /* | |
48 | * The number of non-COMMON commits in rev_list. | |
49 | */ | |
50 | int non_common_revs; | |
51 | }; | |
52 | ||
53 | static int compare(const void *a_, const void *b_, void *unused) | |
54 | { | |
55 | const struct entry *a = a_; | |
56 | const struct entry *b = b_; | |
57 | return compare_commits_by_commit_date(a->commit, b->commit, NULL); | |
58 | } | |
59 | ||
60 | static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark) | |
61 | { | |
62 | struct entry *entry; | |
63 | commit->object.flags |= mark | SEEN; | |
64 | ||
65 | entry = xcalloc(1, sizeof(*entry)); | |
66 | entry->commit = commit; | |
67 | prio_queue_put(&data->rev_list, entry); | |
68 | ||
69 | if (!(mark & COMMON)) | |
70 | data->non_common_revs++; | |
71 | return entry; | |
72 | } | |
73 | ||
74 | static int clear_marks(const char *refname, const struct object_id *oid, | |
75 | int flag, void *cb_data) | |
76 | { | |
7c85ee6c | 77 | struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0); |
42cc7485 JT |
78 | |
79 | if (o && o->type == OBJ_COMMIT) | |
80 | clear_commit_marks((struct commit *)o, | |
81 | COMMON | ADVERTISED | SEEN | POPPED); | |
82 | return 0; | |
83 | } | |
84 | ||
85 | /* | |
86 | * Mark this SEEN commit and all its SEEN ancestors as COMMON. | |
87 | */ | |
88 | static void mark_common(struct data *data, struct commit *c) | |
89 | { | |
90 | struct commit_list *p; | |
91 | ||
92 | if (c->object.flags & COMMON) | |
93 | return; | |
94 | c->object.flags |= COMMON; | |
95 | if (!(c->object.flags & POPPED)) | |
96 | data->non_common_revs--; | |
97 | ||
98 | if (!c->object.parsed) | |
99 | return; | |
100 | for (p = c->parents; p; p = p->next) { | |
101 | if (p->item->object.flags & SEEN) | |
102 | mark_common(data, p->item); | |
103 | } | |
104 | } | |
105 | ||
106 | /* | |
107 | * Ensure that the priority queue has an entry for to_push, and ensure that the | |
108 | * entry has the correct flags and ttl. | |
109 | * | |
110 | * This function returns 1 if an entry was found or created, and 0 otherwise | |
111 | * (because the entry for this commit had already been popped). | |
112 | */ | |
113 | static int push_parent(struct data *data, struct entry *entry, | |
114 | struct commit *to_push) | |
115 | { | |
116 | struct entry *parent_entry; | |
117 | ||
118 | if (to_push->object.flags & SEEN) { | |
119 | int i; | |
120 | if (to_push->object.flags & POPPED) | |
121 | /* | |
122 | * The entry for this commit has already been popped, | |
123 | * due to clock skew. Pretend that this parent does not | |
124 | * exist. | |
125 | */ | |
126 | return 0; | |
127 | /* | |
128 | * Find the existing entry and use it. | |
129 | */ | |
130 | for (i = 0; i < data->rev_list.nr; i++) { | |
131 | parent_entry = data->rev_list.array[i].data; | |
132 | if (parent_entry->commit == to_push) | |
133 | goto parent_found; | |
134 | } | |
135 | BUG("missing parent in priority queue"); | |
136 | parent_found: | |
137 | ; | |
138 | } else { | |
139 | parent_entry = rev_list_push(data, to_push, 0); | |
140 | } | |
141 | ||
142 | if (entry->commit->object.flags & (COMMON | ADVERTISED)) { | |
143 | mark_common(data, to_push); | |
144 | } else { | |
145 | uint16_t new_original_ttl = entry->ttl | |
146 | ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1; | |
147 | uint16_t new_ttl = entry->ttl | |
148 | ? entry->ttl - 1 : new_original_ttl; | |
149 | if (parent_entry->original_ttl < new_original_ttl) { | |
150 | parent_entry->original_ttl = new_original_ttl; | |
151 | parent_entry->ttl = new_ttl; | |
152 | } | |
153 | } | |
154 | ||
155 | return 1; | |
156 | } | |
157 | ||
158 | static const struct object_id *get_rev(struct data *data) | |
159 | { | |
160 | struct commit *to_send = NULL; | |
161 | ||
162 | while (to_send == NULL) { | |
163 | struct entry *entry; | |
164 | struct commit *commit; | |
165 | struct commit_list *p; | |
166 | int parent_pushed = 0; | |
167 | ||
168 | if (data->rev_list.nr == 0 || data->non_common_revs == 0) | |
169 | return NULL; | |
170 | ||
171 | entry = prio_queue_get(&data->rev_list); | |
172 | commit = entry->commit; | |
173 | commit->object.flags |= POPPED; | |
174 | if (!(commit->object.flags & COMMON)) | |
175 | data->non_common_revs--; | |
176 | ||
177 | if (!(commit->object.flags & COMMON) && !entry->ttl) | |
178 | to_send = commit; | |
179 | ||
180 | parse_commit(commit); | |
181 | for (p = commit->parents; p; p = p->next) | |
182 | parent_pushed |= push_parent(data, entry, p->item); | |
183 | ||
184 | if (!(commit->object.flags & COMMON) && !parent_pushed) | |
185 | /* | |
186 | * This commit has no parents, or all of its parents | |
187 | * have already been popped (due to clock skew), so send | |
188 | * it anyway. | |
189 | */ | |
190 | to_send = commit; | |
191 | ||
192 | free(entry); | |
193 | } | |
194 | ||
195 | return &to_send->object.oid; | |
196 | } | |
197 | ||
198 | static void known_common(struct fetch_negotiator *n, struct commit *c) | |
199 | { | |
200 | if (c->object.flags & SEEN) | |
201 | return; | |
202 | rev_list_push(n->data, c, ADVERTISED); | |
203 | } | |
204 | ||
205 | static void add_tip(struct fetch_negotiator *n, struct commit *c) | |
206 | { | |
207 | n->known_common = NULL; | |
208 | if (c->object.flags & SEEN) | |
209 | return; | |
210 | rev_list_push(n->data, c, 0); | |
211 | } | |
212 | ||
213 | static const struct object_id *next(struct fetch_negotiator *n) | |
214 | { | |
215 | n->known_common = NULL; | |
216 | n->add_tip = NULL; | |
217 | return get_rev(n->data); | |
218 | } | |
219 | ||
220 | static int ack(struct fetch_negotiator *n, struct commit *c) | |
221 | { | |
222 | int known_to_be_common = !!(c->object.flags & COMMON); | |
223 | if (!(c->object.flags & SEEN)) | |
224 | die("received ack for commit %s not sent as 'have'\n", | |
225 | oid_to_hex(&c->object.oid)); | |
226 | mark_common(n->data, c); | |
227 | return known_to_be_common; | |
228 | } | |
229 | ||
230 | static void release(struct fetch_negotiator *n) | |
231 | { | |
232 | clear_prio_queue(&((struct data *)n->data)->rev_list); | |
233 | FREE_AND_NULL(n->data); | |
234 | } | |
235 | ||
236 | void skipping_negotiator_init(struct fetch_negotiator *negotiator) | |
237 | { | |
238 | struct data *data; | |
239 | negotiator->known_common = known_common; | |
240 | negotiator->add_tip = add_tip; | |
241 | negotiator->next = next; | |
242 | negotiator->ack = ack; | |
243 | negotiator->release = release; | |
244 | negotiator->data = data = xcalloc(1, sizeof(*data)); | |
245 | data->rev_list.compare = compare; | |
246 | ||
247 | if (marked) | |
248 | for_each_ref(clear_marks, NULL); | |
249 | marked = 1; | |
250 | } |