aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorVlad Yasevich <vladislav.yasevich@hp.com>2008-10-08 17:18:39 -0400
committerDavid S. Miller <davem@davemloft.net>2008-10-08 17:18:39 -0400
commit8e1ee18c332e08bee9d8bd66e63cd564fbf17fc2 (patch)
tree8dace1db660d555eb6e020f301fdfe6cf6c05b80
parent3c689b7320ae6f20dba6a8b71806a6c6fd604ee8 (diff)
sctp: Rework the tsn map to use generic bitmap.
The tsn map currently use is 4K large and is stuck inside the sctp_association structure making memory references REALLY expensive. What we really need is at most 4K worth of bits so the biggest map we would have is 512 bytes. Also, the map is only really usefull when we have gaps to store and report. As such, starting with minimal map of say 32 TSNs (bits) should be enough for normal low-loss operations. We can grow the map by some multiple of 32 along with some extra room any time we receive the TSN which would put us outside of the map boundry. As we close gaps, we can shift the map to rebase it on the latest TSN we've seen. This saves 4088 bytes per association just in the map alone along savings from the now unnecessary structure members. Signed-off-by: Vlad Yasevich <vladislav.yasevich@hp.com> Signed-off-by: David S. Miller <davem@davemloft.net>
-rw-r--r--include/net/sctp/constants.h4
-rw-r--r--include/net/sctp/structs.h1
-rw-r--r--include/net/sctp/tsnmap.h39
-rw-r--r--net/sctp/associola.c9
-rw-r--r--net/sctp/sm_make_chunk.c5
-rw-r--r--net/sctp/sm_sideeffect.c3
-rw-r--r--net/sctp/tsnmap.c331
-rw-r--r--net/sctp/ulpevent.c10
8 files changed, 178 insertions, 224 deletions
diff --git a/include/net/sctp/constants.h b/include/net/sctp/constants.h
index c32ddf0279c8..b05b0557211f 100644
--- a/include/net/sctp/constants.h
+++ b/include/net/sctp/constants.h
@@ -261,7 +261,9 @@ enum { SCTP_ARBITRARY_COOKIE_ECHO_LEN = 200 };
261 * must be less than 65535 (2^16 - 1), or we will have overflow 261 * must be less than 65535 (2^16 - 1), or we will have overflow
262 * problems creating SACK's. 262 * problems creating SACK's.
263 */ 263 */
264#define SCTP_TSN_MAP_SIZE 2048 264#define SCTP_TSN_MAP_INITIAL BITS_PER_LONG
265#define SCTP_TSN_MAP_INCREMENT SCTP_TSN_MAP_INITIAL
266#define SCTP_TSN_MAP_SIZE 4096
265#define SCTP_TSN_MAX_GAP 65535 267#define SCTP_TSN_MAX_GAP 65535
266 268
267/* We will not record more than this many duplicate TSNs between two 269/* We will not record more than this many duplicate TSNs between two
diff --git a/include/net/sctp/structs.h b/include/net/sctp/structs.h
index 94c62e4ddea9..9661d7b765f0 100644
--- a/include/net/sctp/structs.h
+++ b/include/net/sctp/structs.h
@@ -1545,7 +1545,6 @@ struct sctp_association {
1545 * in tsn_map--we get it by calling sctp_tsnmap_get_ctsn(). 1545 * in tsn_map--we get it by calling sctp_tsnmap_get_ctsn().
1546 */ 1546 */
1547 struct sctp_tsnmap tsn_map; 1547 struct sctp_tsnmap tsn_map;
1548 __u8 _map[sctp_tsnmap_storage_size(SCTP_TSN_MAP_SIZE)];
1549 1548
1550 /* Ack State : This flag indicates if the next received 1549 /* Ack State : This flag indicates if the next received
1551 * : packet is to be responded to with a 1550 * : packet is to be responded to with a
diff --git a/include/net/sctp/tsnmap.h b/include/net/sctp/tsnmap.h
index 099211bf998d..6dabbee8bbd3 100644
--- a/include/net/sctp/tsnmap.h
+++ b/include/net/sctp/tsnmap.h
@@ -60,18 +60,7 @@ struct sctp_tsnmap {
60 * It points at one of the two buffers with which we will 60 * It points at one of the two buffers with which we will
61 * ping-pong between. 61 * ping-pong between.
62 */ 62 */
63 __u8 *tsn_map; 63 unsigned long *tsn_map;
64
65 /* This marks the tsn which overflows the tsn_map, when the
66 * cumulative ack point reaches this point we know we can switch
67 * maps (tsn_map and overflow_map swap).
68 */
69 __u32 overflow_tsn;
70
71 /* This is the overflow array for tsn_map.
72 * It points at one of the other ping-pong buffers.
73 */
74 __u8 *overflow_map;
75 64
76 /* This is the TSN at tsn_map[0]. */ 65 /* This is the TSN at tsn_map[0]. */
77 __u32 base_tsn; 66 __u32 base_tsn;
@@ -89,15 +78,15 @@ struct sctp_tsnmap {
89 */ 78 */
90 __u32 cumulative_tsn_ack_point; 79 __u32 cumulative_tsn_ack_point;
91 80
81 /* This is the highest TSN we've marked. */
82 __u32 max_tsn_seen;
83
92 /* This is the minimum number of TSNs we can track. This corresponds 84 /* This is the minimum number of TSNs we can track. This corresponds
93 * to the size of tsn_map. Note: the overflow_map allows us to 85 * to the size of tsn_map. Note: the overflow_map allows us to
94 * potentially track more than this quantity. 86 * potentially track more than this quantity.
95 */ 87 */
96 __u16 len; 88 __u16 len;
97 89
98 /* This is the highest TSN we've marked. */
99 __u32 max_tsn_seen;
100
101 /* Data chunks pending receipt. used by SCTP_STATUS sockopt */ 90 /* Data chunks pending receipt. used by SCTP_STATUS sockopt */
102 __u16 pending_data; 91 __u16 pending_data;
103 92
@@ -110,24 +99,17 @@ struct sctp_tsnmap {
110 99
111 /* Record gap ack block information here. */ 100 /* Record gap ack block information here. */
112 struct sctp_gap_ack_block gabs[SCTP_MAX_GABS]; 101 struct sctp_gap_ack_block gabs[SCTP_MAX_GABS];
113
114 int malloced;
115
116 __u8 raw_map[0];
117}; 102};
118 103
119struct sctp_tsnmap_iter { 104struct sctp_tsnmap_iter {
120 __u32 start; 105 __u32 start;
121}; 106};
122 107
123/* This macro assists in creation of external storage for variable length
124 * internal buffers. We double allocate so the overflow map works.
125 */
126#define sctp_tsnmap_storage_size(count) (sizeof(__u8) * (count) * 2)
127
128/* Initialize a block of memory as a tsnmap. */ 108/* Initialize a block of memory as a tsnmap. */
129struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *, __u16 len, 109struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *, __u16 len,
130 __u32 initial_tsn); 110 __u32 initial_tsn, gfp_t gfp);
111
112void sctp_tsnmap_free(struct sctp_tsnmap *map);
131 113
132/* Test the tracking state of this TSN. 114/* Test the tracking state of this TSN.
133 * Returns: 115 * Returns:
@@ -138,7 +120,7 @@ struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *, __u16 len,
138int sctp_tsnmap_check(const struct sctp_tsnmap *, __u32 tsn); 120int sctp_tsnmap_check(const struct sctp_tsnmap *, __u32 tsn);
139 121
140/* Mark this TSN as seen. */ 122/* Mark this TSN as seen. */
141void sctp_tsnmap_mark(struct sctp_tsnmap *, __u32 tsn); 123int sctp_tsnmap_mark(struct sctp_tsnmap *, __u32 tsn);
142 124
143/* Mark this TSN and all lower as seen. */ 125/* Mark this TSN and all lower as seen. */
144void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn); 126void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn);
@@ -183,10 +165,7 @@ static inline struct sctp_gap_ack_block *sctp_tsnmap_get_gabs(struct sctp_tsnmap
183/* Is there a gap in the TSN map? */ 165/* Is there a gap in the TSN map? */
184static inline int sctp_tsnmap_has_gap(const struct sctp_tsnmap *map) 166static inline int sctp_tsnmap_has_gap(const struct sctp_tsnmap *map)
185{ 167{
186 int has_gap; 168 return (map->cumulative_tsn_ack_point != map->max_tsn_seen);
187
188 has_gap = (map->cumulative_tsn_ack_point != map->max_tsn_seen);
189 return has_gap;
190} 169}
191 170
192/* Mark a duplicate TSN. Note: limit the storage of duplicate TSN 171/* Mark a duplicate TSN. Note: limit the storage of duplicate TSN
diff --git a/net/sctp/associola.c b/net/sctp/associola.c
index abd51cef2413..f4b23043b610 100644
--- a/net/sctp/associola.c
+++ b/net/sctp/associola.c
@@ -283,8 +283,7 @@ static struct sctp_association *sctp_association_init(struct sctp_association *a
283 if (!sctp_ulpq_init(&asoc->ulpq, asoc)) 283 if (!sctp_ulpq_init(&asoc->ulpq, asoc))
284 goto fail_init; 284 goto fail_init;
285 285
286 /* Set up the tsn tracking. */ 286 memset(&asoc->peer.tsn_map, 0, sizeof(struct sctp_tsnmap));
287 sctp_tsnmap_init(&asoc->peer.tsn_map, SCTP_TSN_MAP_SIZE, 0);
288 287
289 asoc->need_ecne = 0; 288 asoc->need_ecne = 0;
290 289
@@ -402,6 +401,8 @@ void sctp_association_free(struct sctp_association *asoc)
402 /* Dispose of any pending chunks on the inqueue. */ 401 /* Dispose of any pending chunks on the inqueue. */
403 sctp_inq_free(&asoc->base.inqueue); 402 sctp_inq_free(&asoc->base.inqueue);
404 403
404 sctp_tsnmap_free(&asoc->peer.tsn_map);
405
405 /* Free ssnmap storage. */ 406 /* Free ssnmap storage. */
406 sctp_ssnmap_free(asoc->ssnmap); 407 sctp_ssnmap_free(asoc->ssnmap);
407 408
@@ -1122,8 +1123,8 @@ void sctp_assoc_update(struct sctp_association *asoc,
1122 asoc->peer.rwnd = new->peer.rwnd; 1123 asoc->peer.rwnd = new->peer.rwnd;
1123 asoc->peer.sack_needed = new->peer.sack_needed; 1124 asoc->peer.sack_needed = new->peer.sack_needed;
1124 asoc->peer.i = new->peer.i; 1125 asoc->peer.i = new->peer.i;
1125 sctp_tsnmap_init(&asoc->peer.tsn_map, SCTP_TSN_MAP_SIZE, 1126 sctp_tsnmap_init(&asoc->peer.tsn_map, SCTP_TSN_MAP_INITIAL,
1126 asoc->peer.i.initial_tsn); 1127 asoc->peer.i.initial_tsn, GFP_ATOMIC);
1127 1128
1128 /* Remove any peer addresses not present in the new association. */ 1129 /* Remove any peer addresses not present in the new association. */
1129 list_for_each_safe(pos, temp, &asoc->peer.transport_addr_list) { 1130 list_for_each_safe(pos, temp, &asoc->peer.transport_addr_list) {
diff --git a/net/sctp/sm_make_chunk.c b/net/sctp/sm_make_chunk.c
index 76726bcff3e9..6dd9b3ef33d0 100644
--- a/net/sctp/sm_make_chunk.c
+++ b/net/sctp/sm_make_chunk.c
@@ -2288,8 +2288,9 @@ int sctp_process_init(struct sctp_association *asoc, sctp_cid_t cid,
2288 } 2288 }
2289 2289
2290 /* Set up the TSN tracking pieces. */ 2290 /* Set up the TSN tracking pieces. */
2291 sctp_tsnmap_init(&asoc->peer.tsn_map, SCTP_TSN_MAP_SIZE, 2291 if (!sctp_tsnmap_init(&asoc->peer.tsn_map, SCTP_TSN_MAP_INITIAL,
2292 asoc->peer.i.initial_tsn); 2292 asoc->peer.i.initial_tsn, gfp))
2293 goto clean_up;
2293 2294
2294 /* RFC 2960 6.5 Stream Identifier and Stream Sequence Number 2295 /* RFC 2960 6.5 Stream Identifier and Stream Sequence Number
2295 * 2296 *
diff --git a/net/sctp/sm_sideeffect.c b/net/sctp/sm_sideeffect.c
index 13d9eea5cf1a..e1d6076b4f59 100644
--- a/net/sctp/sm_sideeffect.c
+++ b/net/sctp/sm_sideeffect.c
@@ -1152,7 +1152,8 @@ static int sctp_cmd_interpreter(sctp_event_t event_type,
1152 1152
1153 case SCTP_CMD_REPORT_TSN: 1153 case SCTP_CMD_REPORT_TSN:
1154 /* Record the arrival of a TSN. */ 1154 /* Record the arrival of a TSN. */
1155 sctp_tsnmap_mark(&asoc->peer.tsn_map, cmd->obj.u32); 1155 error = sctp_tsnmap_mark(&asoc->peer.tsn_map,
1156 cmd->obj.u32);
1156 break; 1157 break;
1157 1158
1158 case SCTP_CMD_REPORT_FWDTSN: 1159 case SCTP_CMD_REPORT_FWDTSN:
diff --git a/net/sctp/tsnmap.c b/net/sctp/tsnmap.c
index f3e58b275905..142ed7ca424d 100644
--- a/net/sctp/tsnmap.c
+++ b/net/sctp/tsnmap.c
@@ -43,37 +43,44 @@
43 */ 43 */
44 44
45#include <linux/types.h> 45#include <linux/types.h>
46#include <linux/bitmap.h>
46#include <net/sctp/sctp.h> 47#include <net/sctp/sctp.h>
47#include <net/sctp/sm.h> 48#include <net/sctp/sm.h>
48 49
49static void sctp_tsnmap_update(struct sctp_tsnmap *map); 50static void sctp_tsnmap_update(struct sctp_tsnmap *map);
50static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off, 51static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
51 __u16 len, __u16 base, 52 __u16 len, __u16 *start, __u16 *end);
52 int *started, __u16 *start, 53static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 gap);
53 int *ended, __u16 *end);
54 54
55/* Initialize a block of memory as a tsnmap. */ 55/* Initialize a block of memory as a tsnmap. */
56struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len, 56struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
57 __u32 initial_tsn) 57 __u32 initial_tsn, gfp_t gfp)
58{ 58{
59 map->tsn_map = map->raw_map; 59 if (!map->tsn_map) {
60 map->overflow_map = map->tsn_map + len; 60 map->tsn_map = kzalloc(len>>3, gfp);
61 map->len = len; 61 if (map->tsn_map == NULL)
62 62 return NULL;
63 /* Clear out a TSN ack status. */ 63
64 memset(map->tsn_map, 0x00, map->len + map->len); 64 map->len = len;
65 } else {
66 bitmap_zero(map->tsn_map, map->len);
67 }
65 68
66 /* Keep track of TSNs represented by tsn_map. */ 69 /* Keep track of TSNs represented by tsn_map. */
67 map->base_tsn = initial_tsn; 70 map->base_tsn = initial_tsn;
68 map->overflow_tsn = initial_tsn + map->len;
69 map->cumulative_tsn_ack_point = initial_tsn - 1; 71 map->cumulative_tsn_ack_point = initial_tsn - 1;
70 map->max_tsn_seen = map->cumulative_tsn_ack_point; 72 map->max_tsn_seen = map->cumulative_tsn_ack_point;
71 map->malloced = 0;
72 map->num_dup_tsns = 0; 73 map->num_dup_tsns = 0;
73 74
74 return map; 75 return map;
75} 76}
76 77
78void sctp_tsnmap_free(struct sctp_tsnmap *map)
79{
80 map->len = 0;
81 kfree(map->tsn_map);
82}
83
77/* Test the tracking state of this TSN. 84/* Test the tracking state of this TSN.
78 * Returns: 85 * Returns:
79 * 0 if the TSN has not yet been seen 86 * 0 if the TSN has not yet been seen
@@ -82,66 +89,69 @@ struct sctp_tsnmap *sctp_tsnmap_init(struct sctp_tsnmap *map, __u16 len,
82 */ 89 */
83int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn) 90int sctp_tsnmap_check(const struct sctp_tsnmap *map, __u32 tsn)
84{ 91{
85 __s32 gap; 92 u32 gap;
86 int dup; 93
94 /* Check to see if this is an old TSN */
95 if (TSN_lte(tsn, map->cumulative_tsn_ack_point))
96 return 1;
97
98 /* Verify that we can hold this TSN and that it will not
99 * overlfow our map
100 */
101 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
102 return -1;
87 103
88 /* Calculate the index into the mapping arrays. */ 104 /* Calculate the index into the mapping arrays. */
89 gap = tsn - map->base_tsn; 105 gap = tsn - map->base_tsn;
90 106
91 /* Verify that we can hold this TSN. */ 107 /* Check to see if TSN has already been recorded. */
92 if (gap >= (/* base */ map->len + /* overflow */ map->len)) { 108 if (gap < map->len && test_bit(gap, map->tsn_map))
93 dup = -1; 109 return 1;
94 goto out;
95 }
96
97 /* Honk if we've already seen this TSN.
98 * We have three cases:
99 * 1. The TSN is ancient or belongs to a previous tsn_map.
100 * 2. The TSN is already marked in the tsn_map.
101 * 3. The TSN is already marked in the tsn_map_overflow.
102 */
103 if (gap < 0 ||
104 (gap < map->len && map->tsn_map[gap]) ||
105 (gap >= map->len && map->overflow_map[gap - map->len]))
106 dup = 1;
107 else 110 else
108 dup = 0; 111 return 0;
109
110out:
111 return dup;
112} 112}
113 113
114 114
115/* Mark this TSN as seen. */ 115/* Mark this TSN as seen. */
116void sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn) 116int sctp_tsnmap_mark(struct sctp_tsnmap *map, __u32 tsn)
117{ 117{
118 __s32 gap; 118 u16 gap;
119 119
120 /* Vacuously mark any TSN which precedes the map base or
121 * exceeds the end of the map.
122 */
123 if (TSN_lt(tsn, map->base_tsn)) 120 if (TSN_lt(tsn, map->base_tsn))
124 return; 121 return 0;
125 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len))
126 return;
127
128 /* Bump the max. */
129 if (TSN_lt(map->max_tsn_seen, tsn))
130 map->max_tsn_seen = tsn;
131 122
132 /* Assert: TSN is in range. */
133 gap = tsn - map->base_tsn; 123 gap = tsn - map->base_tsn;
134 124
135 /* Mark the TSN as received. */ 125 if (gap >= map->len && !sctp_tsnmap_grow(map, gap))
136 if (gap < map->len) 126 return -ENOMEM;
137 map->tsn_map[gap]++;
138 else
139 map->overflow_map[gap - map->len]++;
140 127
141 /* Go fixup any internal TSN mapping variables including 128 if (!sctp_tsnmap_has_gap(map) && gap == 0) {
142 * cumulative_tsn_ack_point. 129 /* In this case the map has no gaps and the tsn we are
143 */ 130 * recording is the next expected tsn. We don't touch
144 sctp_tsnmap_update(map); 131 * the map but simply bump the values.
132 */
133 map->max_tsn_seen++;
134 map->cumulative_tsn_ack_point++;
135 map->base_tsn++;
136 } else {
137 /* Either we already have a gap, or about to record a gap, so
138 * have work to do.
139 *
140 * Bump the max.
141 */
142 if (TSN_lt(map->max_tsn_seen, tsn))
143 map->max_tsn_seen = tsn;
144
145 /* Mark the TSN as received. */
146 set_bit(gap, map->tsn_map);
147
148 /* Go fixup any internal TSN mapping variables including
149 * cumulative_tsn_ack_point.
150 */
151 sctp_tsnmap_update(map);
152 }
153
154 return 0;
145} 155}
146 156
147 157
@@ -160,66 +170,34 @@ SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
160 struct sctp_tsnmap_iter *iter, 170 struct sctp_tsnmap_iter *iter,
161 __u16 *start, __u16 *end) 171 __u16 *start, __u16 *end)
162{ 172{
163 int started, ended; 173 int ended = 0;
164 __u16 start_, end_, offset; 174 __u16 start_ = 0, end_ = 0, offset;
165
166 /* We haven't found a gap yet. */
167 started = ended = 0;
168 175
169 /* If there are no more gap acks possible, get out fast. */ 176 /* If there are no more gap acks possible, get out fast. */
170 if (TSN_lte(map->max_tsn_seen, iter->start)) 177 if (TSN_lte(map->max_tsn_seen, iter->start))
171 return 0; 178 return 0;
172 179
173 /* Search the first mapping array. */ 180 offset = iter->start - map->base_tsn;
174 if (iter->start - map->base_tsn < map->len) { 181 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len,
175 182 &start_, &end_);
176 offset = iter->start - map->base_tsn;
177 sctp_tsnmap_find_gap_ack(map->tsn_map, offset, map->len, 0,
178 &started, &start_, &ended, &end_);
179 }
180
181 /* Do we need to check the overflow map? */
182 if (!ended) {
183 /* Fix up where we'd like to start searching in the
184 * overflow map.
185 */
186 if (iter->start - map->base_tsn < map->len)
187 offset = 0;
188 else
189 offset = iter->start - map->base_tsn - map->len;
190
191 /* Search the overflow map. */
192 sctp_tsnmap_find_gap_ack(map->overflow_map,
193 offset,
194 map->len,
195 map->len,
196 &started, &start_,
197 &ended, &end_);
198 }
199 183
200 /* The Gap Ack Block happens to end at the end of the 184 /* The Gap Ack Block happens to end at the end of the map. */
201 * overflow map. 185 if (start_ && !end_)
202 */ 186 end_ = map->len - 1;
203 if (started && !ended) {
204 ended++;
205 end_ = map->len + map->len - 1;
206 }
207 187
208 /* If we found a Gap Ack Block, return the start and end and 188 /* If we found a Gap Ack Block, return the start and end and
209 * bump the iterator forward. 189 * bump the iterator forward.
210 */ 190 */
211 if (ended) { 191 if (end_) {
212 /* Fix up the start and end based on the 192 /* Fix up the start and end based on the
213 * Cumulative TSN Ack offset into the map. 193 * Cumulative TSN Ack which is always 1 behind base.
214 */ 194 */
215 int gap = map->cumulative_tsn_ack_point - 195 *start = start_ + 1;
216 map->base_tsn; 196 *end = end_ + 1;
217
218 *start = start_ - gap;
219 *end = end_ - gap;
220 197
221 /* Move the iterator forward. */ 198 /* Move the iterator forward. */
222 iter->start = map->cumulative_tsn_ack_point + *end + 1; 199 iter->start = map->cumulative_tsn_ack_point + *end + 1;
200 ended = 1;
223 } 201 }
224 202
225 return ended; 203 return ended;
@@ -228,35 +206,33 @@ SCTP_STATIC int sctp_tsnmap_next_gap_ack(const struct sctp_tsnmap *map,
228/* Mark this and any lower TSN as seen. */ 206/* Mark this and any lower TSN as seen. */
229void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn) 207void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
230{ 208{
231 __s32 gap; 209 u32 gap;
232 210
233 /* Vacuously mark any TSN which precedes the map base or
234 * exceeds the end of the map.
235 */
236 if (TSN_lt(tsn, map->base_tsn)) 211 if (TSN_lt(tsn, map->base_tsn))
237 return; 212 return;
238 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len)) 213 if (!TSN_lt(tsn, map->base_tsn + SCTP_TSN_MAP_SIZE))
239 return; 214 return;
240 215
241 /* Bump the max. */ 216 /* Bump the max. */
242 if (TSN_lt(map->max_tsn_seen, tsn)) 217 if (TSN_lt(map->max_tsn_seen, tsn))
243 map->max_tsn_seen = tsn; 218 map->max_tsn_seen = tsn;
244 219
245 /* Assert: TSN is in range. */
246 gap = tsn - map->base_tsn + 1; 220 gap = tsn - map->base_tsn + 1;
247 221
248 /* Mark the TSNs as received. */ 222 map->base_tsn += gap;
249 if (gap <= map->len) 223 map->cumulative_tsn_ack_point += gap;
250 memset(map->tsn_map, 0x01, gap); 224 if (gap >= map->len) {
251 else { 225 /* If our gap is larger then the map size, just
252 memset(map->tsn_map, 0x01, map->len); 226 * zero out the map.
253 memset(map->overflow_map, 0x01, (gap - map->len)); 227 */
228 bitmap_zero(map->tsn_map, map->len);
229 } else {
230 /* If the gap is smaller then the map size,
231 * shift the map by 'gap' bits and update further.
232 */
233 bitmap_shift_right(map->tsn_map, map->tsn_map, gap, map->len);
234 sctp_tsnmap_update(map);
254 } 235 }
255
256 /* Go fixup any internal TSN mapping variables including
257 * cumulative_tsn_ack_point.
258 */
259 sctp_tsnmap_update(map);
260} 236}
261 237
262/******************************************************************** 238/********************************************************************
@@ -268,27 +244,19 @@ void sctp_tsnmap_skip(struct sctp_tsnmap *map, __u32 tsn)
268 */ 244 */
269static void sctp_tsnmap_update(struct sctp_tsnmap *map) 245static void sctp_tsnmap_update(struct sctp_tsnmap *map)
270{ 246{
271 __u32 ctsn; 247 u16 len;
272 248 unsigned long zero_bit;
273 ctsn = map->cumulative_tsn_ack_point; 249
274 do { 250
275 ctsn++; 251 len = map->max_tsn_seen - map->cumulative_tsn_ack_point;
276 if (ctsn == map->overflow_tsn) { 252 zero_bit = find_first_zero_bit(map->tsn_map, len);
277 /* Now tsn_map must have been all '1's, 253 if (!zero_bit)
278 * so we swap the map and check the overflow table 254 return; /* The first 0-bit is bit 0. nothing to do */
279 */ 255
280 __u8 *tmp = map->tsn_map; 256 map->base_tsn += zero_bit;
281 memset(tmp, 0, map->len); 257 map->cumulative_tsn_ack_point += zero_bit;
282 map->tsn_map = map->overflow_map;
283 map->overflow_map = tmp;
284
285 /* Update the tsn_map boundaries. */
286 map->base_tsn += map->len;
287 map->overflow_tsn += map->len;
288 }
289 } while (map->tsn_map[ctsn - map->base_tsn]);
290 258
291 map->cumulative_tsn_ack_point = ctsn - 1; /* Back up one. */ 259 bitmap_shift_right(map->tsn_map, map->tsn_map, zero_bit, map->len);
292} 260}
293 261
294/* How many data chunks are we missing from our peer? 262/* How many data chunks are we missing from our peer?
@@ -299,31 +267,19 @@ __u16 sctp_tsnmap_pending(struct sctp_tsnmap *map)
299 __u32 max_tsn = map->max_tsn_seen; 267 __u32 max_tsn = map->max_tsn_seen;
300 __u32 base_tsn = map->base_tsn; 268 __u32 base_tsn = map->base_tsn;
301 __u16 pending_data; 269 __u16 pending_data;
302 __s32 gap, start, end, i; 270 u32 gap, i;
303 271
304 pending_data = max_tsn - cum_tsn; 272 pending_data = max_tsn - cum_tsn;
305 gap = max_tsn - base_tsn; 273 gap = max_tsn - base_tsn;
306 274
307 if (gap <= 0 || gap >= (map->len + map->len)) 275 if (gap == 0 || gap >= map->len)
308 goto out; 276 goto out;
309 277
310 start = ((cum_tsn >= base_tsn) ? (cum_tsn - base_tsn + 1) : 0); 278 for (i = 0; i < gap+1; i++) {
311 end = ((gap > map->len ) ? map->len : gap + 1); 279 if (test_bit(i, map->tsn_map))
312
313 for (i = start; i < end; i++) {
314 if (map->tsn_map[i])
315 pending_data--; 280 pending_data--;
316 } 281 }
317 282
318 if (gap >= map->len) {
319 start = 0;
320 end = gap - map->len + 1;
321 for (i = start; i < end; i++) {
322 if (map->overflow_map[i])
323 pending_data--;
324 }
325 }
326
327out: 283out:
328 return pending_data; 284 return pending_data;
329} 285}
@@ -334,10 +290,8 @@ out:
334 * The flags "started" and "ended" tell is if we found the beginning 290 * The flags "started" and "ended" tell is if we found the beginning
335 * or (respectively) the end of a Gap Ack Block. 291 * or (respectively) the end of a Gap Ack Block.
336 */ 292 */
337static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off, 293static void sctp_tsnmap_find_gap_ack(unsigned long *map, __u16 off,
338 __u16 len, __u16 base, 294 __u16 len, __u16 *start, __u16 *end)
339 int *started, __u16 *start,
340 int *ended, __u16 *end)
341{ 295{
342 int i = off; 296 int i = off;
343 297
@@ -348,49 +302,36 @@ static void sctp_tsnmap_find_gap_ack(__u8 *map, __u16 off,
348 /* Also, stop looking past the maximum TSN seen. */ 302 /* Also, stop looking past the maximum TSN seen. */
349 303
350 /* Look for the start. */ 304 /* Look for the start. */
351 if (!(*started)) { 305 i = find_next_bit(map, len, off);
352 for (; i < len; i++) { 306 if (i < len)
353 if (map[i]) { 307 *start = i;
354 (*started)++;
355 *start = base + i;
356 break;
357 }
358 }
359 }
360 308
361 /* Look for the end. */ 309 /* Look for the end. */
362 if (*started) { 310 if (*start) {
363 /* We have found the start, let's find the 311 /* We have found the start, let's find the
364 * end. If we find the end, break out. 312 * end. If we find the end, break out.
365 */ 313 */
366 for (; i < len; i++) { 314 i = find_next_zero_bit(map, len, i);
367 if (!map[i]) { 315 if (i < len)
368 (*ended)++; 316 *end = i - 1;
369 *end = base + i - 1;
370 break;
371 }
372 }
373 } 317 }
374} 318}
375 319
376/* Renege that we have seen a TSN. */ 320/* Renege that we have seen a TSN. */
377void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn) 321void sctp_tsnmap_renege(struct sctp_tsnmap *map, __u32 tsn)
378{ 322{
379 __s32 gap; 323 u32 gap;
380 324
381 if (TSN_lt(tsn, map->base_tsn)) 325 if (TSN_lt(tsn, map->base_tsn))
382 return; 326 return;
383 if (!TSN_lt(tsn, map->base_tsn + map->len + map->len)) 327 /* Assert: TSN is in range. */
328 if (!TSN_lt(tsn, map->base_tsn + map->len))
384 return; 329 return;
385 330
386 /* Assert: TSN is in range. */
387 gap = tsn - map->base_tsn; 331 gap = tsn - map->base_tsn;
388 332
389 /* Pretend we never saw the TSN. */ 333 /* Pretend we never saw the TSN. */
390 if (gap < map->len) 334 clear_bit(gap, map->tsn_map);
391 map->tsn_map[gap] = 0;
392 else
393 map->overflow_map[gap - map->len] = 0;
394} 335}
395 336
396/* How many gap ack blocks do we have recorded? */ 337/* How many gap ack blocks do we have recorded? */
@@ -416,3 +357,27 @@ __u16 sctp_tsnmap_num_gabs(struct sctp_tsnmap *map)
416 } 357 }
417 return gabs; 358 return gabs;
418} 359}
360
361static int sctp_tsnmap_grow(struct sctp_tsnmap *map, u16 gap)
362{
363 unsigned long *new;
364 unsigned long inc;
365 u16 len;
366
367 if (gap >= SCTP_TSN_MAP_SIZE)
368 return 0;
369
370 inc = ALIGN((gap - map->len),BITS_PER_LONG) + SCTP_TSN_MAP_INCREMENT;
371 len = min_t(u16, map->len + inc, SCTP_TSN_MAP_SIZE);
372
373 new = kzalloc(len>>3, GFP_ATOMIC);
374 if (!new)
375 return 0;
376
377 bitmap_copy(new, map->tsn_map, map->max_tsn_seen - map->base_tsn);
378 kfree(map->tsn_map);
379 map->tsn_map = new;
380 map->len = len;
381
382 return 1;
383}
diff --git a/net/sctp/ulpevent.c b/net/sctp/ulpevent.c
index a1f654aea268..5f186ca550d7 100644
--- a/net/sctp/ulpevent.c
+++ b/net/sctp/ulpevent.c
@@ -713,7 +713,9 @@ struct sctp_ulpevent *sctp_ulpevent_make_rcvmsg(struct sctp_association *asoc,
713 /* Now that all memory allocations for this chunk succeeded, we 713 /* Now that all memory allocations for this chunk succeeded, we
714 * can mark it as received so the tsn_map is updated correctly. 714 * can mark it as received so the tsn_map is updated correctly.
715 */ 715 */
716 sctp_tsnmap_mark(&asoc->peer.tsn_map, ntohl(chunk->subh.data_hdr->tsn)); 716 if (sctp_tsnmap_mark(&asoc->peer.tsn_map,
717 ntohl(chunk->subh.data_hdr->tsn)))
718 goto fail_mark;
717 719
718 /* First calculate the padding, so we don't inadvertently 720 /* First calculate the padding, so we don't inadvertently
719 * pass up the wrong length to the user. 721 * pass up the wrong length to the user.
@@ -755,8 +757,12 @@ struct sctp_ulpevent *sctp_ulpevent_make_rcvmsg(struct sctp_association *asoc,
755 event->msg_flags |= chunk->chunk_hdr->flags; 757 event->msg_flags |= chunk->chunk_hdr->flags;
756 event->iif = sctp_chunk_iif(chunk); 758 event->iif = sctp_chunk_iif(chunk);
757 759
758fail:
759 return event; 760 return event;
761
762fail_mark:
763 kfree_skb(skb);
764fail:
765 return NULL;
760} 766}
761 767
762/* Create a partial delivery related event. 768/* Create a partial delivery related event.