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