-
Notifications
You must be signed in to change notification settings - Fork 19
/
Dynamic.hs
390 lines (342 loc) · 12.3 KB
/
Dynamic.hs
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RecordWildCards #-}
module Network.HPACK.Table.Dynamic (
DynamicTable(..)
, newDynamicTableForEncoding
, newDynamicTableForDecoding
, renewDynamicTable
, huffmanDecoder
, printDynamicTable
, isDynamicTableEmpty
, isSuitableSize
, TableSizeAction(..)
, needChangeTableSize
, setLimitForEncoding
, resetLimitForEncoding
, insertEntry
, toDynamicEntry
, CodeInfo(..)
, withDynamicTableForEncoding
, withDynamicTableForDecoding
, toIndexedEntry
, fromHIndexToIndex
, getRevIndex
) where
import Control.Exception (throwIO)
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.IO (IOArray, newArray)
import qualified Data.ByteString.Char8 as BS
import Data.IORef
import Imports
import Network.HPACK.Huffman
import Network.HPACK.Table.Entry
import Network.HPACK.Table.RevIndex
import Network.HPACK.Table.Static
import Network.HPACK.Types
----------------------------------------------------------------
-- For decoder
{-# INLINE toIndexedEntry #-}
toIndexedEntry :: DynamicTable -> Index -> IO Entry
toIndexedEntry dyntbl idx
| idx <= 0 = throwIO $ IndexOverrun idx
| idx <= staticTableSize = return $ toStaticEntry idx
| otherwise = toDynamicEntry dyntbl idx
-- For encoder
{-# INLINE fromHIndexToIndex #-}
fromHIndexToIndex :: DynamicTable -> HIndex -> IO Index
fromHIndexToIndex _ (SIndex idx) = return idx
fromHIndexToIndex DynamicTable{..} (DIndex didx) = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
x <- adj maxN (didx - off)
return $ x + staticTableSize
----------------------------------------------------------------
type Table = IOArray Index Entry
{-
offset
v
+-+-+-+-+-+-+-+-+
| | | |z|y|x| | |
+-+-+-+-+-+-+-+-+
1 2 3 (numOfEntries = 3)
After insertion:
offset
v
+-+-+-+-+-+-+-+-+
| | |w|z|y|x| | |
+-+-+-+-+-+-+-+-+
1 2 3 4 (numOfEntries = 4)
-}
data CodeInfo =
EncodeInfo RevIndex -- Reverse index
-- The value informed by SETTINGS_HEADER_TABLE_SIZE.
-- If 'Nothing', dynamic table size update is not necessary.
-- Otherwise, dynamic table size update is sent
-- and this value should be set to 'Nothing'.
(IORef (Maybe Size))
| DecodeInfo HuffmanDecoder
(IORef Size) -- The limit size
-- | Type for dynamic table.
data DynamicTable = DynamicTable {
codeInfo :: CodeInfo
-- | An array
, circularTable :: IORef Table
-- | Start point
, offset :: IORef Index
-- | The current number of entries
, numOfEntries :: IORef Int
-- | The size of the array
, maxNumOfEntries :: IORef Int
-- | The current dynamic table size (defined in HPACK)
, dynamicTableSize :: IORef Size
-- | The max dynamic table size (defined in HPACK)
, maxDynamicTableSize :: IORef Size
}
{-# INLINE adj #-}
adj :: Int -> Int -> IO Int
adj maxN x
| maxN == 0 = throwIO TooSmallTableSize
| otherwise = let ret = (x + maxN) `mod` maxN
in return ret
huffmanDecoder :: DynamicTable -> HuffmanDecoder
huffmanDecoder DynamicTable{..} = dec
where
DecodeInfo dec _ = codeInfo
----------------------------------------------------------------
-- | Printing 'DynamicTable'.
printDynamicTable :: DynamicTable -> IO ()
printDynamicTable DynamicTable{..} = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
let beg = off + 1
end = off + n
tbl <- readIORef circularTable
es <- mapM (adj maxN >=> unsafeRead tbl) [beg .. end]
let ts = zip [1..] es
mapM_ printEntry ts
dsize <- readIORef dynamicTableSize
maxdsize <- readIORef maxDynamicTableSize
putStrLn $ " Table size: " ++ show dsize ++ "/" ++ show maxdsize
printEntry :: (Index,Entry) -> IO ()
printEntry (i,e) = do
putStr "[ "
putStr $ show i
putStr "] (s = "
putStr $ show $ entrySize e
putStr ") "
BS.putStr $ entryHeaderName e
putStr ": "
BS.putStrLn $ entryHeaderValue e
----------------------------------------------------------------
isDynamicTableEmpty :: DynamicTable -> IO Bool
isDynamicTableEmpty DynamicTable{..} = do
n <- readIORef numOfEntries
return $ n == 0
isSuitableSize :: Size -> DynamicTable -> IO Bool
isSuitableSize siz DynamicTable{..} = do
let DecodeInfo _ limref = codeInfo
lim <- readIORef limref
return $ siz <= lim
data TableSizeAction = Keep | Change Size | Ignore Size
needChangeTableSize :: DynamicTable -> IO TableSizeAction
needChangeTableSize DynamicTable{..} = do
let EncodeInfo _ limref = codeInfo
mlim <- readIORef limref
maxsiz <- readIORef maxDynamicTableSize
return $ case mlim of
Nothing -> Keep
Just lim
| lim < maxsiz -> Change lim
| otherwise -> Ignore maxsiz
-- | When SETTINGS_HEADER_TABLE_SIZE is received from a peer,
-- its value should be set by this function.
setLimitForEncoding :: Size -> DynamicTable -> IO ()
setLimitForEncoding siz DynamicTable{..} = do
let EncodeInfo _ limref = codeInfo
writeIORef limref $ Just siz
resetLimitForEncoding :: DynamicTable -> IO ()
resetLimitForEncoding DynamicTable{..} = do
let EncodeInfo _ limref = codeInfo
writeIORef limref Nothing
----------------------------------------------------------------
-- | Creating 'DynamicTable' for encoding.
newDynamicTableForEncoding :: Size -- ^ The dynamic table size
-> IO DynamicTable
newDynamicTableForEncoding maxsiz = do
rev <- newRevIndex
lim <- newIORef Nothing
let info = EncodeInfo rev lim
newDynamicTable maxsiz info
-- | Creating 'DynamicTable' for decoding.
newDynamicTableForDecoding :: Size -- ^ The dynamic table size
-> Size -- ^ The size of temporary buffer for Huffman decoding
-> IO DynamicTable
newDynamicTableForDecoding maxsiz huftmpsiz = do
lim <- newIORef maxsiz
buf <- mallocPlainForeignPtrBytes huftmpsiz
let decoder = decodeH buf huftmpsiz
info = DecodeInfo decoder lim
newDynamicTable maxsiz info
newDynamicTable :: Size -> CodeInfo -> IO DynamicTable
newDynamicTable maxsiz info = do
tbl <- newArray (0,end) dummyEntry
DynamicTable info <$> newIORef tbl -- circularTable
<*> newIORef end -- offset
<*> newIORef 0 -- numOfEntries
<*> newIORef maxN -- maxNumOfEntries
<*> newIORef 0 -- dynamicTableSize
<*> newIORef maxsiz -- maxDynamicTableSize
where
maxN = maxNumbers maxsiz
end = maxN - 1
-- | Renewing 'DynamicTable' with necessary entries copied.
renewDynamicTable :: Size -> DynamicTable -> IO ()
renewDynamicTable maxsiz dyntbl@DynamicTable{..} = do
renew <- shouldRenew dyntbl maxsiz
when renew $ do
entries <- getEntries dyntbl
let maxN = maxNumbers maxsiz
end = maxN - 1
newtbl <- newArray (0,end) dummyEntry
writeIORef circularTable newtbl
writeIORef offset end
writeIORef numOfEntries 0
writeIORef maxNumOfEntries maxN
writeIORef dynamicTableSize 0
writeIORef maxDynamicTableSize maxsiz
case codeInfo of
EncodeInfo rev _ -> renewRevIndex rev
_ -> return ()
copyEntries dyntbl entries
getEntries :: DynamicTable -> IO [Entry]
getEntries DynamicTable{..} = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
table <- readIORef circularTable
let readTable i = adj maxN (off + i) >>= unsafeRead table
forM [1 .. n] readTable
copyEntries :: DynamicTable -> [Entry] -> IO ()
copyEntries _ [] = return ()
copyEntries dyntbl@DynamicTable{..} (e:es) = do
dsize <- readIORef dynamicTableSize
maxdsize <- readIORef maxDynamicTableSize
when (dsize + entrySize e <= maxdsize) $ do
insertEnd e dyntbl
copyEntries dyntbl es
-- | Is the size of 'DynamicTable' really changed?
shouldRenew :: DynamicTable -> Size -> IO Bool
shouldRenew DynamicTable{..} maxsiz = do
maxdsize <- readIORef maxDynamicTableSize
return $ maxdsize /= maxsiz
----------------------------------------------------------------
-- | Creating 'DynamicTable' for encoding,
-- performing the action and
-- clearing the 'DynamicTable'.
withDynamicTableForEncoding :: Size -- ^ The dynamic table size
-> (DynamicTable -> IO a)
-> IO a
withDynamicTableForEncoding maxsiz action =
newDynamicTableForEncoding maxsiz >>= action
-- | Creating 'DynamicTable' for decoding,
-- performing the action and
-- clearing the 'DynamicTable'.
withDynamicTableForDecoding :: Size -- ^ The dynamic table size
-> Size -- ^ The size of temporary buffer for Huffman
-> (DynamicTable -> IO a)
-> IO a
withDynamicTableForDecoding maxsiz huftmpsiz action =
newDynamicTableForDecoding maxsiz huftmpsiz >>= action
----------------------------------------------------------------
-- | Inserting 'Entry' to 'DynamicTable'.
-- New 'DynamicTable', the largest new 'Index'
-- and a set of dropped OLD 'Index'
-- are returned.
insertEntry :: Entry -> DynamicTable -> IO ()
insertEntry e dyntbl@DynamicTable{..} = do
insertFront e dyntbl
es <- adjustTableSize dyntbl
case codeInfo of
EncodeInfo rev _ -> deleteRevIndexList es rev
_ -> return ()
insertFront :: Entry -> DynamicTable -> IO ()
insertFront e DynamicTable{..} = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
dsize <- readIORef dynamicTableSize
table <- readIORef circularTable
let i = off
dsize' = dsize + entrySize e
if maxN == 0
then return ()
else do
off' <- adj maxN (off - 1)
unsafeWrite table i e
writeIORef offset off'
writeIORef numOfEntries $ n + 1
writeIORef dynamicTableSize dsize'
case codeInfo of
EncodeInfo rev _ -> insertRevIndex e (DIndex i) rev
_ -> return ()
adjustTableSize :: DynamicTable -> IO [Entry]
adjustTableSize dyntbl@DynamicTable{..} = adjust []
where
adjust :: [Entry] -> IO [Entry]
adjust es = do
dsize <- readIORef dynamicTableSize
maxdsize <- readIORef maxDynamicTableSize
if dsize <= maxdsize then
return es
else do
e <- removeEnd dyntbl
adjust (e:es)
----------------------------------------------------------------
insertEnd :: Entry -> DynamicTable -> IO ()
insertEnd e DynamicTable{..} = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
dsize <- readIORef dynamicTableSize
table <- readIORef circularTable
i <- adj maxN (off + n + 1)
let dsize' = dsize + entrySize e
unsafeWrite table i e
writeIORef numOfEntries $ n + 1
writeIORef dynamicTableSize dsize'
case codeInfo of
EncodeInfo rev _ -> insertRevIndex e (DIndex i) rev
_ -> return ()
----------------------------------------------------------------
removeEnd :: DynamicTable -> IO Entry
removeEnd DynamicTable{..} = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
i <- adj maxN (off + n)
table <- readIORef circularTable
e <- unsafeRead table i
unsafeWrite table i dummyEntry -- let the entry GCed
dsize <- readIORef dynamicTableSize
let dsize' = dsize - entrySize e
writeIORef numOfEntries (n - 1)
writeIORef dynamicTableSize dsize'
return e
----------------------------------------------------------------
{-# INLINE toDynamicEntry #-}
toDynamicEntry :: DynamicTable -> Index -> IO Entry
toDynamicEntry DynamicTable{..} idx = do
maxN <- readIORef maxNumOfEntries
off <- readIORef offset
n <- readIORef numOfEntries
when (idx > n + staticTableSize) $ throwIO $ IndexOverrun idx
didx <- adj maxN (idx + off - staticTableSize)
table <- readIORef circularTable
unsafeRead table didx
----------------------------------------------------------------
{-# INLINE getRevIndex #-}
getRevIndex :: DynamicTable-> RevIndex
getRevIndex DynamicTable{..} = rev
where
EncodeInfo rev _ = codeInfo