Merge branch 'master' of master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6
[deliverable/linux.git] / net / sched / sch_sfq.c
CommitLineData
1da177e4
LT
1/*
2 * net/sched/sch_sfq.c Stochastic Fairness Queueing discipline.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 */
11
1da177e4 12#include <linux/module.h>
1da177e4
LT
13#include <linux/types.h>
14#include <linux/kernel.h>
15#include <linux/jiffies.h>
16#include <linux/string.h>
1da177e4
LT
17#include <linux/in.h>
18#include <linux/errno.h>
1da177e4 19#include <linux/init.h>
1da177e4 20#include <linux/ipv6.h>
1da177e4 21#include <linux/skbuff.h>
32740ddc 22#include <linux/jhash.h>
5a0e3ad6 23#include <linux/slab.h>
0ba48053
PM
24#include <net/ip.h>
25#include <net/netlink.h>
1da177e4
LT
26#include <net/pkt_sched.h>
27
28
29/* Stochastic Fairness Queuing algorithm.
30 =======================================
31
32 Source:
33 Paul E. McKenney "Stochastic Fairness Queuing",
34 IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
35
36 Paul E. McKenney "Stochastic Fairness Queuing",
37 "Interworking: Research and Experience", v.2, 1991, p.113-131.
38
39
40 See also:
41 M. Shreedhar and George Varghese "Efficient Fair
42 Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
43
44
10297b99 45 This is not the thing that is usually called (W)FQ nowadays.
1da177e4
LT
46 It does not use any timestamp mechanism, but instead
47 processes queues in round-robin order.
48
49 ADVANTAGE:
50
51 - It is very cheap. Both CPU and memory requirements are minimal.
52
53 DRAWBACKS:
54
10297b99 55 - "Stochastic" -> It is not 100% fair.
1da177e4
LT
56 When hash collisions occur, several flows are considered as one.
57
58 - "Round-robin" -> It introduces larger delays than virtual clock
59 based schemes, and should not be used for isolating interactive
60 traffic from non-interactive. It means, that this scheduler
61 should be used as leaf of CBQ or P3, which put interactive traffic
62 to higher priority band.
63
64 We still need true WFQ for top level CSZ, but using WFQ
65 for the best effort traffic is absolutely pointless:
66 SFQ is superior for this purpose.
67
68 IMPLEMENTATION:
69 This implementation limits maximal queue length to 128;
70 maximal mtu to 2^15-1; number of hash buckets to 1024.
71 The only goal of this restrictions was that all data
72 fit into one 4K page :-). Struct sfq_sched_data is
73 organized in anti-cache manner: all the data for a bucket
74 are scattered over different locations. This is not good,
75 but it allowed me to put it into 4K.
76
77 It is easy to increase these values, but not in flight. */
78
79#define SFQ_DEPTH 128
80#define SFQ_HASH_DIVISOR 1024
81
82/* This type should contain at least SFQ_DEPTH*2 values */
83typedef unsigned char sfq_index;
84
85struct sfq_head
86{
87 sfq_index next;
88 sfq_index prev;
89};
90
91struct sfq_sched_data
92{
93/* Parameters */
94 int perturb_period;
95 unsigned quantum; /* Allotment per round: MUST BE >= MTU */
96 int limit;
97
98/* Variables */
7d2681a6 99 struct tcf_proto *filter_list;
1da177e4 100 struct timer_list perturb_timer;
32740ddc 101 u32 perturbation;
1da177e4
LT
102 sfq_index tail; /* Index of current slot in round */
103 sfq_index max_depth; /* Maximal depth */
104
105 sfq_index ht[SFQ_HASH_DIVISOR]; /* Hash table */
106 sfq_index next[SFQ_DEPTH]; /* Active slots link */
107 short allot[SFQ_DEPTH]; /* Current allotment per slot */
108 unsigned short hash[SFQ_DEPTH]; /* Hash value indexed by slots */
109 struct sk_buff_head qs[SFQ_DEPTH]; /* Slot queue */
110 struct sfq_head dep[SFQ_DEPTH*2]; /* Linked list of slots, indexed by depth */
111};
112
113static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
114{
32740ddc 115 return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
1da177e4
LT
116}
117
118static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
119{
120 u32 h, h2;
121
122 switch (skb->protocol) {
60678040 123 case htons(ETH_P_IP):
1da177e4 124 {
f2f00981 125 const struct iphdr *iph;
b9959c2e 126 int poff;
f2f00981
CG
127
128 if (!pskb_network_may_pull(skb, sizeof(*iph)))
129 goto err;
130 iph = ip_hdr(skb);
0eae88f3
ED
131 h = (__force u32)iph->daddr;
132 h2 = (__force u32)iph->saddr ^ iph->protocol;
b9959c2e
CG
133 if (iph->frag_off & htons(IP_MF|IP_OFFSET))
134 break;
135 poff = proto_ports_offset(iph->protocol);
136 if (poff >= 0 &&
137 pskb_network_may_pull(skb, iph->ihl * 4 + 4 + poff)) {
138 iph = ip_hdr(skb);
139 h2 ^= *(u32*)((void *)iph + iph->ihl * 4 + poff);
140 }
1da177e4
LT
141 break;
142 }
60678040 143 case htons(ETH_P_IPV6):
1da177e4 144 {
f2f00981 145 struct ipv6hdr *iph;
b9959c2e 146 int poff;
f2f00981
CG
147
148 if (!pskb_network_may_pull(skb, sizeof(*iph)))
149 goto err;
150 iph = ipv6_hdr(skb);
0eae88f3
ED
151 h = (__force u32)iph->daddr.s6_addr32[3];
152 h2 = (__force u32)iph->saddr.s6_addr32[3] ^ iph->nexthdr;
b9959c2e
CG
153 poff = proto_ports_offset(iph->nexthdr);
154 if (poff >= 0 &&
155 pskb_network_may_pull(skb, sizeof(*iph) + 4 + poff)) {
156 iph = ipv6_hdr(skb);
157 h2 ^= *(u32*)((void *)iph + sizeof(*iph) + poff);
158 }
1da177e4
LT
159 break;
160 }
161 default:
f2f00981 162err:
0eae88f3 163 h = (unsigned long)skb_dst(skb) ^ (__force u32)skb->protocol;
6f9e98f7 164 h2 = (unsigned long)skb->sk;
1da177e4 165 }
6f9e98f7 166
1da177e4
LT
167 return sfq_fold_hash(q, h, h2);
168}
169
7d2681a6
PM
170static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
171 int *qerr)
172{
173 struct sfq_sched_data *q = qdisc_priv(sch);
174 struct tcf_result res;
175 int result;
176
177 if (TC_H_MAJ(skb->priority) == sch->handle &&
178 TC_H_MIN(skb->priority) > 0 &&
179 TC_H_MIN(skb->priority) <= SFQ_HASH_DIVISOR)
180 return TC_H_MIN(skb->priority);
181
182 if (!q->filter_list)
183 return sfq_hash(q, skb) + 1;
184
c27f339a 185 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
7d2681a6
PM
186 result = tc_classify(skb, q->filter_list, &res);
187 if (result >= 0) {
188#ifdef CONFIG_NET_CLS_ACT
189 switch (result) {
190 case TC_ACT_STOLEN:
191 case TC_ACT_QUEUED:
378a2f09 192 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
7d2681a6
PM
193 case TC_ACT_SHOT:
194 return 0;
195 }
196#endif
197 if (TC_H_MIN(res.classid) <= SFQ_HASH_DIVISOR)
198 return TC_H_MIN(res.classid);
199 }
200 return 0;
201}
202
1da177e4
LT
203static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
204{
205 sfq_index p, n;
206 int d = q->qs[x].qlen + SFQ_DEPTH;
207
208 p = d;
209 n = q->dep[d].next;
210 q->dep[x].next = n;
211 q->dep[x].prev = p;
212 q->dep[p].next = q->dep[n].prev = x;
213}
214
215static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
216{
217 sfq_index p, n;
218
219 n = q->dep[x].next;
220 p = q->dep[x].prev;
221 q->dep[p].next = n;
222 q->dep[n].prev = p;
223
224 if (n == p && q->max_depth == q->qs[x].qlen + 1)
225 q->max_depth--;
226
227 sfq_link(q, x);
228}
229
230static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
231{
232 sfq_index p, n;
233 int d;
234
235 n = q->dep[x].next;
236 p = q->dep[x].prev;
237 q->dep[p].next = n;
238 q->dep[n].prev = p;
239 d = q->qs[x].qlen;
240 if (q->max_depth < d)
241 q->max_depth = d;
242
243 sfq_link(q, x);
244}
245
246static unsigned int sfq_drop(struct Qdisc *sch)
247{
248 struct sfq_sched_data *q = qdisc_priv(sch);
249 sfq_index d = q->max_depth;
250 struct sk_buff *skb;
251 unsigned int len;
252
253 /* Queue is full! Find the longest slot and
254 drop a packet from it */
255
256 if (d > 1) {
6f9e98f7 257 sfq_index x = q->dep[d + SFQ_DEPTH].next;
1da177e4 258 skb = q->qs[x].prev;
0abf77e5 259 len = qdisc_pkt_len(skb);
1da177e4
LT
260 __skb_unlink(skb, &q->qs[x]);
261 kfree_skb(skb);
262 sfq_dec(q, x);
263 sch->q.qlen--;
264 sch->qstats.drops++;
f5539eb8 265 sch->qstats.backlog -= len;
1da177e4
LT
266 return len;
267 }
268
269 if (d == 1) {
270 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
271 d = q->next[q->tail];
272 q->next[q->tail] = q->next[d];
1da177e4 273 skb = q->qs[d].prev;
0abf77e5 274 len = qdisc_pkt_len(skb);
1da177e4
LT
275 __skb_unlink(skb, &q->qs[d]);
276 kfree_skb(skb);
277 sfq_dec(q, d);
278 sch->q.qlen--;
279 q->ht[q->hash[d]] = SFQ_DEPTH;
280 sch->qstats.drops++;
f5539eb8 281 sch->qstats.backlog -= len;
1da177e4
LT
282 return len;
283 }
284
285 return 0;
286}
287
288static int
6f9e98f7 289sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
1da177e4
LT
290{
291 struct sfq_sched_data *q = qdisc_priv(sch);
7d2681a6 292 unsigned int hash;
1da177e4 293 sfq_index x;
7f3ff4f6 294 int uninitialized_var(ret);
7d2681a6
PM
295
296 hash = sfq_classify(skb, sch, &ret);
297 if (hash == 0) {
c27f339a 298 if (ret & __NET_XMIT_BYPASS)
7d2681a6
PM
299 sch->qstats.drops++;
300 kfree_skb(skb);
301 return ret;
302 }
303 hash--;
1da177e4
LT
304
305 x = q->ht[hash];
306 if (x == SFQ_DEPTH) {
307 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
308 q->hash[x] = hash;
309 }
6f9e98f7 310
32740ddc
AK
311 /* If selected queue has length q->limit, this means that
312 * all another queues are empty and that we do simple tail drop,
313 * i.e. drop _this_ packet.
314 */
315 if (q->qs[x].qlen >= q->limit)
316 return qdisc_drop(skb, sch);
317
0abf77e5 318 sch->qstats.backlog += qdisc_pkt_len(skb);
1da177e4
LT
319 __skb_queue_tail(&q->qs[x], skb);
320 sfq_inc(q, x);
321 if (q->qs[x].qlen == 1) { /* The flow is new */
322 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
1da177e4 323 q->next[x] = x;
1da177e4
LT
324 } else {
325 q->next[x] = q->next[q->tail];
326 q->next[q->tail] = x;
1da177e4 327 }
aa3e2199
ED
328 q->tail = x;
329 q->allot[x] = q->quantum;
1da177e4 330 }
5588b40d 331 if (++sch->q.qlen <= q->limit) {
0abf77e5 332 sch->bstats.bytes += qdisc_pkt_len(skb);
1da177e4 333 sch->bstats.packets++;
9871e50e 334 return NET_XMIT_SUCCESS;
1da177e4
LT
335 }
336
337 sfq_drop(sch);
338 return NET_XMIT_CN;
339}
340
48a8f519
PM
341static struct sk_buff *
342sfq_peek(struct Qdisc *sch)
343{
344 struct sfq_sched_data *q = qdisc_priv(sch);
345 sfq_index a;
1da177e4 346
48a8f519
PM
347 /* No active slots */
348 if (q->tail == SFQ_DEPTH)
349 return NULL;
1da177e4 350
48a8f519
PM
351 a = q->next[q->tail];
352 return skb_peek(&q->qs[a]);
353}
1da177e4
LT
354
355static struct sk_buff *
6f9e98f7 356sfq_dequeue(struct Qdisc *sch)
1da177e4
LT
357{
358 struct sfq_sched_data *q = qdisc_priv(sch);
359 struct sk_buff *skb;
aa3e2199 360 sfq_index a, next_a;
1da177e4
LT
361
362 /* No active slots */
363 if (q->tail == SFQ_DEPTH)
364 return NULL;
365
aa3e2199 366 a = q->next[q->tail];
1da177e4
LT
367
368 /* Grab packet */
369 skb = __skb_dequeue(&q->qs[a]);
370 sfq_dec(q, a);
371 sch->q.qlen--;
0abf77e5 372 sch->qstats.backlog -= qdisc_pkt_len(skb);
1da177e4
LT
373
374 /* Is the slot empty? */
375 if (q->qs[a].qlen == 0) {
376 q->ht[q->hash[a]] = SFQ_DEPTH;
aa3e2199
ED
377 next_a = q->next[a];
378 if (a == next_a) {
1da177e4
LT
379 q->tail = SFQ_DEPTH;
380 return skb;
381 }
aa3e2199 382 q->next[q->tail] = next_a;
0abf77e5 383 } else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
1da177e4 384 q->allot[a] += q->quantum;
aa3e2199 385 q->tail = a;
1da177e4
LT
386 }
387 return skb;
388}
389
390static void
6f9e98f7 391sfq_reset(struct Qdisc *sch)
1da177e4
LT
392{
393 struct sk_buff *skb;
394
395 while ((skb = sfq_dequeue(sch)) != NULL)
396 kfree_skb(skb);
397}
398
399static void sfq_perturbation(unsigned long arg)
400{
6f9e98f7 401 struct Qdisc *sch = (struct Qdisc *)arg;
1da177e4
LT
402 struct sfq_sched_data *q = qdisc_priv(sch);
403
d46f8dd8 404 q->perturbation = net_random();
1da177e4 405
32740ddc
AK
406 if (q->perturb_period)
407 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
1da177e4
LT
408}
409
1e90474c 410static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
1da177e4
LT
411{
412 struct sfq_sched_data *q = qdisc_priv(sch);
1e90474c 413 struct tc_sfq_qopt *ctl = nla_data(opt);
5e50da01 414 unsigned int qlen;
1da177e4 415
1e90474c 416 if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
1da177e4
LT
417 return -EINVAL;
418
419 sch_tree_lock(sch);
5ce2d488 420 q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
6f9e98f7 421 q->perturb_period = ctl->perturb_period * HZ;
1da177e4 422 if (ctl->limit)
32740ddc 423 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
1da177e4 424
5e50da01 425 qlen = sch->q.qlen;
5588b40d 426 while (sch->q.qlen > q->limit)
1da177e4 427 sfq_drop(sch);
5e50da01 428 qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
1da177e4
LT
429
430 del_timer(&q->perturb_timer);
431 if (q->perturb_period) {
32740ddc 432 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
d46f8dd8 433 q->perturbation = net_random();
1da177e4
LT
434 }
435 sch_tree_unlock(sch);
436 return 0;
437}
438
1e90474c 439static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
1da177e4
LT
440{
441 struct sfq_sched_data *q = qdisc_priv(sch);
442 int i;
443
d3e99483 444 q->perturb_timer.function = sfq_perturbation;
c19a28e1 445 q->perturb_timer.data = (unsigned long)sch;
d3e99483 446 init_timer_deferrable(&q->perturb_timer);
1da177e4 447
6f9e98f7 448 for (i = 0; i < SFQ_HASH_DIVISOR; i++)
1da177e4 449 q->ht[i] = SFQ_DEPTH;
6f9e98f7
SH
450
451 for (i = 0; i < SFQ_DEPTH; i++) {
1da177e4 452 skb_queue_head_init(&q->qs[i]);
6f9e98f7
SH
453 q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
454 q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
1da177e4 455 }
6f9e98f7 456
32740ddc 457 q->limit = SFQ_DEPTH - 1;
1da177e4
LT
458 q->max_depth = 0;
459 q->tail = SFQ_DEPTH;
460 if (opt == NULL) {
5ce2d488 461 q->quantum = psched_mtu(qdisc_dev(sch));
1da177e4 462 q->perturb_period = 0;
d46f8dd8 463 q->perturbation = net_random();
1da177e4
LT
464 } else {
465 int err = sfq_change(sch, opt);
466 if (err)
467 return err;
468 }
6f9e98f7
SH
469
470 for (i = 0; i < SFQ_DEPTH; i++)
1da177e4
LT
471 sfq_link(q, i);
472 return 0;
473}
474
475static void sfq_destroy(struct Qdisc *sch)
476{
477 struct sfq_sched_data *q = qdisc_priv(sch);
7d2681a6 478
ff31ab56 479 tcf_destroy_chain(&q->filter_list);
980c478d
JP
480 q->perturb_period = 0;
481 del_timer_sync(&q->perturb_timer);
1da177e4
LT
482}
483
484static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
485{
486 struct sfq_sched_data *q = qdisc_priv(sch);
27a884dc 487 unsigned char *b = skb_tail_pointer(skb);
1da177e4
LT
488 struct tc_sfq_qopt opt;
489
490 opt.quantum = q->quantum;
6f9e98f7 491 opt.perturb_period = q->perturb_period / HZ;
1da177e4
LT
492
493 opt.limit = q->limit;
494 opt.divisor = SFQ_HASH_DIVISOR;
cdec7e50 495 opt.flows = q->limit;
1da177e4 496
1e90474c 497 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
1da177e4
LT
498
499 return skb->len;
500
1e90474c 501nla_put_failure:
dc5fc579 502 nlmsg_trim(skb, b);
1da177e4
LT
503 return -1;
504}
505
41065fba
JP
506static struct Qdisc *sfq_leaf(struct Qdisc *sch, unsigned long arg)
507{
508 return NULL;
509}
510
7d2681a6
PM
511static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
512{
513 return 0;
514}
515
eb4a5527
JP
516static unsigned long sfq_bind(struct Qdisc *sch, unsigned long parent,
517 u32 classid)
518{
519 return 0;
520}
521
da7115d9
JP
522static void sfq_put(struct Qdisc *q, unsigned long cl)
523{
524}
525
7d2681a6
PM
526static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
527{
528 struct sfq_sched_data *q = qdisc_priv(sch);
529
530 if (cl)
531 return NULL;
532 return &q->filter_list;
533}
534
94de78d1
PM
535static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
536 struct sk_buff *skb, struct tcmsg *tcm)
537{
538 tcm->tcm_handle |= TC_H_MIN(cl);
539 return 0;
540}
541
542static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
543 struct gnet_dump *d)
544{
545 struct sfq_sched_data *q = qdisc_priv(sch);
546 sfq_index idx = q->ht[cl-1];
c4266263
ED
547 struct sk_buff_head *list = &q->qs[idx];
548 struct gnet_stats_queue qs = { .qlen = list->qlen };
94de78d1 549 struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };
c4266263
ED
550 struct sk_buff *skb;
551
552 skb_queue_walk(list, skb)
553 qs.backlog += qdisc_pkt_len(skb);
94de78d1
PM
554
555 if (gnet_stats_copy_queue(d, &qs) < 0)
556 return -1;
557 return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
558}
559
7d2681a6
PM
560static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
561{
94de78d1
PM
562 struct sfq_sched_data *q = qdisc_priv(sch);
563 unsigned int i;
564
565 if (arg->stop)
566 return;
567
568 for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
569 if (q->ht[i] == SFQ_DEPTH ||
570 arg->count < arg->skip) {
571 arg->count++;
572 continue;
573 }
574 if (arg->fn(sch, i + 1, arg) < 0) {
575 arg->stop = 1;
576 break;
577 }
578 arg->count++;
579 }
7d2681a6
PM
580}
581
582static const struct Qdisc_class_ops sfq_class_ops = {
41065fba 583 .leaf = sfq_leaf,
7d2681a6 584 .get = sfq_get,
da7115d9 585 .put = sfq_put,
7d2681a6 586 .tcf_chain = sfq_find_tcf,
eb4a5527 587 .bind_tcf = sfq_bind,
da7115d9 588 .unbind_tcf = sfq_put,
94de78d1
PM
589 .dump = sfq_dump_class,
590 .dump_stats = sfq_dump_class_stats,
7d2681a6
PM
591 .walk = sfq_walk,
592};
593
20fea08b 594static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
7d2681a6 595 .cl_ops = &sfq_class_ops,
1da177e4
LT
596 .id = "sfq",
597 .priv_size = sizeof(struct sfq_sched_data),
598 .enqueue = sfq_enqueue,
599 .dequeue = sfq_dequeue,
48a8f519 600 .peek = sfq_peek,
1da177e4
LT
601 .drop = sfq_drop,
602 .init = sfq_init,
603 .reset = sfq_reset,
604 .destroy = sfq_destroy,
605 .change = NULL,
606 .dump = sfq_dump,
607 .owner = THIS_MODULE,
608};
609
610static int __init sfq_module_init(void)
611{
612 return register_qdisc(&sfq_qdisc_ops);
613}
10297b99 614static void __exit sfq_module_exit(void)
1da177e4
LT
615{
616 unregister_qdisc(&sfq_qdisc_ops);
617}
618module_init(sfq_module_init)
619module_exit(sfq_module_exit)
620MODULE_LICENSE("GPL");
This page took 0.68587 seconds and 5 git commands to generate.