160088 2016-07-22 10:41:50 -0700 Simplify ThreadData* management for a Bucket inside ParkingLot.cpp 2016-07-22 14:04:45 -0700 1 1 1 Unclassified WebKit Web Template Framework WebKit Nightly Build Unspecified Unspecified NEW P2 Normal --- 1 rajeevmisraforapple webkit-unassigned benjamin cdumez cmarcelo commit-queue fpizlo saam oldest_to_newest 1213621 0 rajeevmisraforapple 2016-07-22 10:41:50 -0700 Simplify ThreadData* management for a Bucket inside ParkingLot.cpp 1213640 1 284349 rajeevmisraforapple 2016-07-22 11:14:05 -0700 Created attachment 284349 Patch 1213732 2 rajeevmisraforapple 2016-07-22 13:53:12 -0700 This is not a regular patch but a kind of POC to see if I should spend more time in this direction. Currently, management of ThreadData* inside Bucket of HashTable in ParkingLot.cpp needs at least 3 pointers (As with any Singly LinkedList being used as Queue/FIFO): 1) queueHead 2) queueTail 3) nextInQueue and during dequeuing we need more pointers 4) currentPtr 5) previous At a given time, juggling with 5 pointers and ensuring each is pointing to correct location is error prone task (even though common for LinkedList) and probably hard to understand/maintain in future. If we don't worry about fairness of dequeue of enqueued threads aka we don't guarantee FIFO order, we could use a simple BitMap to keep track on equeued ThreadData* in Bucket (kind of simplified vector). We initially create BitMap of 32 size (size of uint32_t) which is expandable (or we could even start with smaller size is required). Size of this is capped by number of threads in system (and if unlucky, all thread waiting on same address in which case this BitMap size = number of threads) We create Array of ThreadData*, and BitMap entries indicate which entries in this Array is valid (BitMap is our gold reference) If BitMap entry is 0, that slot in Array is free. If BitMap entry for location is 1, that slot in Array is occupied by Valid ThreadData* entry. This made dequeue/enqueue logic very simple. equeue: Search for first 0 in BitMap and put ThreadData* in that slot dequeue : Search for first 1 in BitMap and clear that bit after extracting ThreadData* from it. (This also gets rid of clever abomination :-) which is common for LinkedList remove and not to mention hard to understand) Ignore Result: now does not do any manipulation to pointer. RemoveAndStop & RemoveAndContinue Result are now just clearing bit and moving on. This patch is just POC, so I have ignored efficiency and some good programming practices so please feel free to point them out. If most of the cases are where 1 thread has lock and another waiting for lock, FIFO probably does not add much, in which case BitMap approach is probably better as we don't need to keep track of any pointers. Thread Starvation is definitely possible in some scenario with this approach, such as Thread_1, and Thread_2 equeued, and then Thread_1 dequeued, and Thread_3 enqueued at first place (enqueue logic looks at first available slot by looking at first 0 bit) and then Thread_3 dequeued and Thread_4 enqueued at first place and so on and Thread_2 starves. In real world things are generally more random so above map not happen that often. IMO, If FIFO overhead is much more than BitMap, we could sacrifice FIFO for better code/efficiency. If FIFO is absolutely must during dequeue, this POC is DOA. 1213734 3 284349 fpizlo 2016-07-22 14:04:45 -0700 Comment on attachment 284349 Patch View in context: https://bugs.webkit.org/attachment.cgi?id=284349&action=review I don't like this change. It makes the code more confusing, and I believe it's a regression since we want FIFO ordering. > Source/WTF/ChangeLog:32 > + If we don't worry about fairness of dequeue of enqueued threads > + aka we don't guranntee FIFO order, we could use a simple > + BitMap to keep track on equeued ThreadData* in Bucket > + (kind of simplied vector). I disagree, we want FIFO order. 284349 2016-07-22 11:14:05 -0700 2016-07-22 14:04:45 -0700 Patch bug-160088-20160722111303.patch text/plain 14911 rajeevmisraforapple SW5kZXg6IFNvdXJjZS9XVEYvQ2hhbmdlTG9nCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIFNvdXJjZS9XVEYvQ2hh bmdlTG9nCShyZXZpc2lvbiAyMDM2MDIpCisrKyBTb3VyY2UvV1RGL0NoYW5nZUxvZwkod29ya2lu ZyBjb3B5KQpAQCAtMSwzICsxLDg4IEBACisyMDE2LTA3LTIyICBSYWplZXYgTWlzcmEgIDxyYWpl ZXZtaXNyYWZvcmFwcGxlQGdtYWlsLmNvbT4KKworICAgICAgICBTaW1wbGlmeSBUaHJlYWREYXRh KiBtYW5hZ2VtZW50IGZvciBhIEJ1Y2tldCBpbnNpZGUgUGFya2luZ0xvdC5jcHAKKyAgICAgICAg aHR0cHM6Ly9idWdzLndlYmtpdC5vcmcvc2hvd19idWcuY2dpP2lkPTE2MDA4OAorCisgICAgICAg IFJldmlld2VkIGJ5IE5PQk9EWSAoT09QUyEpLgorCisgICAgICAgIFRoaXMgaXMgbm90IGEgcmVn dWxhciBwYXRjaCBidXQgYSBraW5kIG9mIFBPQyB0byBzZWUgaWYKKyAgICAgICAgSSBzaG91bGQg c3BlbmQgbW9yZSB0aW1lIGluIHRoaXMgZGlyZWN0aW9uLgorCisgICAgICAgIEN1cnJlbnRseSBt YW5hZ2VtZW50IG9mIFRocmVhZERhdGEqIGluc2lkZSBCdWNrZXQgbmVlZHMKKyAgICAgICAgYXQg bGVhc3QgMyBwb2ludGVycyAoQXMgd2l0aCBhbnkgU2luZ2x5IExpbmtlZExpc3QgYmVpbmcKKyAg ICAgICAgdXNpbmcgUXVldWUpOgorCisgICAgICAgIDEpIHF1ZXVlSGVhZAorICAgICAgICAyKSBx dWV1ZVRhaWwKKyAgICAgICAgMykgbmV4dEluUXVldWUKKworICAgICAgICBhbmQgZHVyaW5nIGRl cXVldWluZyB3ZSBuZWVkIG1vcmUgcG9pbnRlcnMKKworICAgICAgICA0KSBjdXJyZW50UHRyCisg ICAgICAgIDUpIHByZXZpb3VzCisKKyAgICAgICAgU28gYXQgYSBnaXZlbiB0aW1lLCBqdWdnbGlu ZyB3aXRoIDUgcG9pbnRlcnMKKyAgICAgICAgYW5kIGVuc3VyaW5nIGVhY2ggaXMgcG9pbnRpbmcg dG8gY29ycmVjdCBsb2NhdGlvbgorICAgICAgICBpcyBlcnJvciBwcm9uZSB0YXNrIChldmVuIHRo b3VnaCBjb21tb24gZm9yIExpbmtlZExpc3QpCisgICAgICAgIGFuZCBwcm9iYWJseSBoYXJkIHRv IG1haW50YWluIGluIGZ1dHVyZS4KKyAgICAgCisgICAgICAgIElmIHdlIGRvbid0IHdvcnJ5IGFi b3V0IGZhaXJuZXNzIG9mIGRlcXVldWUgb2YgZW5xdWV1ZWQgdGhyZWFkcworICAgICAgICBha2Eg d2UgZG9uJ3QgZ3VyYW5udGVlIEZJRk8gb3JkZXIsIHdlIGNvdWxkIHVzZSBhIHNpbXBsZQorICAg ICAgICBCaXRNYXAgdG8ga2VlcCB0cmFjayBvbiBlcXVldWVkIFRocmVhZERhdGEqIGluIEJ1Y2tl dAorICAgICAgICAoa2luZCBvZiBzaW1wbGllZCB2ZWN0b3IpLiAKKyAKKyAgICAgICAgV2UgaW5p dGlhbGx5IGNyZWF0ZSBCaXRNYXAgb2YgMzIgc2l6ZSAoc2l6ZSBvZiB1aW50MzJfdCkKKyAgICAg ICAgd2hpY2ggaXMgZXhwYW5kYWJsZSAob3Igd2UgY291bGQgZXZlbiBzdGFydCB3aXRoIHNtYWxs ZXIgc2l6ZQorICAgICAgICBpcyByZXF1aXJlZCkuICBTaXplIG9mIHRoaXMgaXMgY2FwcGVkIGJ5 IG51bWJlciBvZiB0aHJlYWRzCisgICAgICAgIGluIHN5c3RlbSAoYW5kIGlmIHVubHVja3ksIGFs bCB0aHJlYWQgd2FpdGluZyBvbiBzYW1lIGFkZHJlc3MKKyAgICAgICAgaW4gd2hpY2ggY2FzZSB0 aGlzIEJpdE1hcCBzaXplID0gbnVtYmVyIG9mIHRocmVhZHMpCisKKyAgICAgICAgV2UgY3JlYXRl IEFycmF5IG9mIFRocmVhZERhdGEqLCBhbmQgQml0TWFwIGVudHJpZXMgaW5kaWNhdGUKKyAgICAg ICAgd2hpY2ggZW50cmllcyBpbiB0aGlzIEFycmF5IGlzIHZhbGlkIChCaXRNYXAgaXMgb3VyIGdv bGQgcmVmZXJlbmNlKSAKKyAgICAgICAgSWYgQml0TWFwIGVudHJ5IGlzIDAsIHRoYXQgc2xvdCBp biBBcnJheSBpcyBmcmVlLiBJZiBCaXRNYXAKKyAgICAgICAgZW50cnkgZm9yIGxvY2F0aW9uIGlz IDEsIHRoYXQgc2xvdCBpbiBBcnJheSBpcyBvY2N1cGllZCBieSBWYWxpZAorICAgICAgICBUaHJl YWREYXRhKiBlbnRyeS4KKworICAgICAgICBUaGlzIG1hZGUgZGVxdWV1ZS9lbnF1ZXVlIGxvZ2lj IHZlcnkgc2ltcGxlLiAKKworICAgICAgICBlcXVldWU6IFNlYXJjaCBmb3IgZmlyc3QgMCBpbiBC aXRNYXAgYW5kIHB1dCBUaHJlYWREYXRhKiBpbiB0aGF0IHNsb3QKKyAgICAgICAgZGVxdWV1ZSA6 IFNlcmFjaCBmb3IgZmlyc3QgMSBpbiBCaXRNYXAgYW5kIGNsZWFyIHRoYXQgYml0IGFmdGVyIGV4 dHJhY3RpbmcKKyAgICAgICAgICAgICAgICAgIFRocmVhZERhdGEqIGZyb20gaXQuIChBbHNvIGdl dCByaWQgb2YgY2xldmVyIGFib21pbmF0aW9uIDotKQorICAgICAgICAgICAgICAgICAgd2hpY2gg aXMgY29tbW9uIGZvciBMaW5rZWRMaXN0IHJlbW92ZSBhbmQgbm90IHRvIG1lbnRpb24gaGFyZAor ICAgICAgICAgICAgICAgICAgdG8gdW5kZXJzdGFuZCkgCisgICAgICAgIAorICAgICAgICBSZW1v dmVBbmRJZ25vcmUgbm93IGRvZXMgbm90IGRvIGFueSBtYW5pcHVsYXRpb24gdG8gcG9pbnRlciBh bmQgaXMganVzdAorICAgICAgICBub29wLgorICAgICAgICBSZW1vdmVBbmRTdG9wICYgUmVtb3Zl QW5kQ29udGludWUgYXJlIG5vdyBqdXN0IGNsZWFyaW5nIGJpdCBhbmQgbW92aW5nIG9uCisKKyAg ICAgICAgVGhpcyBwYXRjaCBpcyBqdXN0IFBPQywgc28gSSBoYXZlIGlnbm9yZWQgZWZmaWNpZW5j eSBhbmQgc29tZSBnb29kCisgICAgICAgIHByb2dyYW1taW5nIHByYWN0aWNlcyBzbyBwbGVhc2Ug ZmVlbCBmcmVlIHRvIHBvaW50IHRoZW0gb3V0LgorCisgICAgICAgIElmIG1vc3Qgb2YgdGhlIGNh c2VzIGFyZSB3aGVyZSAxIHRocmVhZCBoYXMgbG9jayBhbmQgYW5vdGhlciB3YWl0aW5nIGZvciBs b2NrLAorICAgICAgICBGSUZPIHByb2JhYmx5IGRvZXMgbm90IGFkZCBtdWNoLCBpbiB3aGljaCBj YXNlIEJpdE1hcCBhcHByb2FjaCBpcyBwcm9iYWJseQorICAgICAgICBiZXR0ZXIgYXMgd2UgZG9u dCBuZWVkIHRvIGtlZXAgdHJhY2sgb2YgYW55IHBvaW50ZXJzLgorCisgICAgICAgIFRocmVhZCBT dHJ2YXRpb24gaXMgZGVmaW5pdGVseSBwb3NzaWJsZSBpbiBzb21lIHNjZW5hcmlvIHdpdGggdGhp cyBhcHByb2FjaAorICAgICAgICBzdWNoIGFzIFRocmVhZF8xLCBhbmQgVGhyZWFkXzIgZXF1ZXVl ZCwgYW5kIHRoZW4gVGhyZWFkXzEgZGVxdWV1ZWQsIGFuZAorICAgICAgICBUaHJlYWRfMyBlbnF1 ZXVlZCBhdCBmaXJzdCBwbGFjZSBhbmQgdGhlbiBUaHJlYWRfMyBkZXF1ZXVlZCBhbmQgVGhyZWFk XzQKKyAgICAgICAgZW5xdWV1ZWQgYXQgZmlyc3QgcGxhY2UgYW5kIHNvIG9uIGFuZCBUaHJlYWRf MiBzdGF2ZXMuICAKKyAgICAgICAgSW4gcmVhbCB3b3JsZCB0aGluZ3MgYXJlIGdlbmVyYWxseSBz byByYW5kb20gdGhhdCB0aGlzIGtpbmQgb2Ygc3BlY2lmaWMgb3JkZXIgCisgICAgICAgIGlzIGhh cmQgdG8gZmluZC4KKworICAgICAgICBJTU8sIElmIEZJRk8gb3ZlcmhlYWQgaXMgbXVjaCBtb3Jl IHRoYW4gQml0TWFwLCB3ZSBjb3VsZCBzYWNyaWZpY2UgRklGTworICAgICAgICBmb3IgYmV0dGVy IGNvZGUvZWZmaWNpZW5jeS4KKworICAgICAgICBJZiBGSUZPIGlzIGFic29sdXRlbHkgbXVzdCBk dXJpbmcgZGVxdWV1ZSwgdGhpcyBQT0MgaXMgRE9BLgorCisgICAgICAgICogd3RmL0Zhc3RCaXRW ZWN0b3IuaDoKKyAgICAgICAgKFdURjo6RmFzdEJpdFZlY3Rvcjo6Z2V0KToKKyAgICAgICAgKFdU Rjo6RmFzdEJpdFZlY3Rvcjo6ZmZzKToKKyAgICAgICAgKFdURjo6RmFzdEJpdFZlY3Rvcjo6ZmZ6 KToKKyAgICAgICAgKFdURjo6RmFzdEJpdFZlY3Rvcjo6Yml0Q291bnQpOgorICAgICAgICAqIHd0 Zi9QYXJraW5nTG90LmNwcDoKKyAgICAgICAgKFdURjo6UGFya2luZ0xvdDo6cGFya0NvbmRpdGlv bmFsbHlJbXBsKToKKyAgICAgICAgKFdURjo6UGFya2luZ0xvdDo6Zm9yRWFjaCk6CisKIDIwMTYt MDctMjEgIE15bGVzIEMuIE1heGZpZWxkICA8bW1heGZpZWxkQGFwcGxlLmNvbT4KIAogICAgICAg ICBbbWFjT1NdIENhcmV0IHBsYWNlbWVudCBvY2N1cnMgaW4gdGhlIG1pZGRsZSBvZiBuZXcgZW1v amkgZ3JvdXAgY2FuZGlkYXRlcwpJbmRleDogU291cmNlL1dURi93dGYvRmFzdEJpdFZlY3Rvci5o Cj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09 PT09PT09PT09PT0KLS0tIFNvdXJjZS9XVEYvd3RmL0Zhc3RCaXRWZWN0b3IuaAkocmV2aXNpb24g MjAzNDczKQorKysgU291cmNlL1dURi93dGYvRmFzdEJpdFZlY3Rvci5oCSh3b3JraW5nIGNvcHkp CkBAIC0xNzIsNiArMTcyLDc0IEBAIHB1YmxpYzoKICAgICAgICAgcmV0dXJuICEhKG1fYXJyYXlb aSA+PiA1XSAmICgxIDw8IChpICYgMzEpKSk7CiAgICAgfQogICAgIAorICAgIC8vIGZpcnN0IHNl dCBiaXQgYWZ0ZXIgaW5kZXggKGluY2x1ZGluZyBpbmRleCkKKyAgICAvLyBpdCByZXR1cm5zIGlu ZGV4IG9mIG5leHQgc2V0IGJpdCArIDEKKyAgICAvLyAwIHJldHVybnMgbWVhbnMgbm90IGZvdW5k CisgICAgc2l6ZV90IGZmcyhzaXplX3QgaW5kZXgpIGNvbnN0CisgICAgeworICAgICAgICBzaXpl X3Qgc3RhcnRJbmRleCA9IChpbmRleCAmIH4weDFmdSk7CisgICAgICAgIHNpemVfdCByZXN1bHQg PSBzdGFydEluZGV4OworICAgICAgICBzaXplX3QgbGVuZ3RoID0gYXJyYXlMZW5ndGgoKTsKKyAg ICAgICAgdWludDMyX3QgdmFsID0gbV9hcnJheVtpbmRleCA+PiA1XTsKKyAgICAgICAgc2l6ZV90 IGxvY2FsSW5kZXggPSBpbmRleCAmIDB4MWZ1OworICAgICAgICAvLyBzd2l0Y2ggb2ZmIGFsbCBi aXRzIGJlZm9yZSBpbmRleAorICAgICAgICB2YWwgPSB2YWwgJiB+KCgxIDw8IGxvY2FsSW5kZXgp IC0gMSk7CisgICAgICAgIGlmICghdmFsKSB7CisgICAgICAgICAgICByZXN1bHQgKz0gMzI7Cisg ICAgICAgICAgICBmb3IgKHVuc2lnbmVkIGkgPSAoaW5kZXggPj4gNSkgKyAxIDsgaSA8IGxlbmd0 aDsgaSsrKSB7CisgICAgICAgICAgICAgICAgLy8gaWYgbV9hcnJheVtpXSBpcyAwLCB0aGVyZSBp cyBubyBob3BlIG9mIGZpbmRpbmcgMSBpbiBpdAorICAgICAgICAgICAgICAgIGlmICghbV9hcnJh eVtpXSkKKyAgICAgICAgICAgICAgICAgICAgcmVzdWx0ICs9IDMyOworICAgICAgICAgICAgICAg IGVsc2UgeworICAgICAgICAgICAgICAgICAgICByZXN1bHQgKz0gX19idWlsdGluX2ZmcyhtX2Fy cmF5W2ldKTsKKyAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHJlc3VsdCA8PSBtX251bUJpdHMg PyByZXN1bHQgOiAwOworICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgIH0KKyAgICAgICAg fSBlbHNlIHsKKyAgICAgICAgICAgIHJlc3VsdCArPSBfX2J1aWx0aW5fZmZzKHZhbCk7CisgICAg ICAgICAgICByZXR1cm4gcmVzdWx0IDw9IG1fbnVtQml0cyA/IHJlc3VsdCA6IDA7CisgICAgICAg IH0KKyAgICAgICAgcmV0dXJuIDA7CisgICAgfQorICAgIAorICAgIC8vIHJldHVybiBpbmRleCBv ZiBmaXJzdCBvbiBiaXQsIGluZGV4IHN0YXJ0cyBmcm9tIDEKKyAgICAvLyAwIHJldHVybiBtZWFu cyBub3QgZm91bmQKKyAgICBzaXplX3QgZmZzKCkgY29uc3QKKyAgICB7CisgICAgICAgIHNpemVf dCByZXN1bHQgPSAwOworICAgICAgICBzaXplX3QgbGVuZ3RoID0gYXJyYXlMZW5ndGgoKTsKKyAg ICAgICAgZm9yICh1bnNpZ25lZCBpID0gMCA7IGkgPCBsZW5ndGg7IGkrKykgeworICAgICAgICAg ICAgLy8gaWYgbV9hcnJheVtpXSBpcyAwLCB0aGVyZSBpcyBubyBob3BlIG9mIGZpbmRpbmcgMSBp biBpdAorICAgICAgICAgICAgaWYgKCFtX2FycmF5W2ldKQorICAgICAgICAgICAgICAgIHJlc3Vs dCArPSAzMjsKKyAgICAgICAgICAgIGVsc2UgeworICAgICAgICAgICAgICAgIHJlc3VsdCArPSBf X2J1aWx0aW5fZmZzKG1fYXJyYXlbaV0pOworICAgICAgICAgICAgICAgIHJldHVybiByZXN1bHQg PD0gbV9udW1CaXRzID8gcmVzdWx0IDogMDsKKyAgICAgICAgICAgIH0KKyAgICAgICAgfQorICAg ICAgICByZXR1cm4gMDsKKyAgICB9CisgICAgCisgICAgLy8gcmV0dXJuIGluZGV4IG9mIGZpcnN0 IG9mZiBiaXQsIGluZGV4IHN0YXJ0cyBmcm9tIDEKKyAgICAvLyAwIHJldHVybiBtZWFucyBub3Qg Zm91bmQKKyAgICBzaXplX3QgZmZ6KCkgY29uc3QKKyAgICB7CisgICAgICAgIHNpemVfdCByZXN1 bHQgPSAwOworICAgICAgICBzaXplX3QgbGVuZ3RoID0gYXJyYXlMZW5ndGgoKTsKKyAgICAgICAg Zm9yICh1bnNpZ25lZCBpID0gMCA7IGkgPCBsZW5ndGg7IGkrKykgeworICAgICAgICAgICAgdWlu dDMyX3QgdmFsID0gbV9hcnJheVtpXTsKKyAgICAgICAgICAgIC8vIHR1cm4gcmlnaHQgbW9zdCAw IGJpdCBvbgorICAgICAgICAgICAgdmFsID0gfnZhbCAmICh2YWwgKyAxKTsKKyAgICAgICAgICAg IGlmICghdmFsKQorICAgICAgICAgICAgICAgIHJlc3VsdCArPSAzMjsKKyAgICAgICAgICAgIGVs c2UgeworICAgICAgICAgICAgICAgIHJlc3VsdCArPSBfX2J1aWx0aW5fZmZzKHZhbCk7CisgICAg ICAgICAgICAgICAgcmV0dXJuIHJlc3VsdCA8PSBtX251bUJpdHMgPyByZXN1bHQgOiAwOworICAg ICAgICAgICAgfQorICAgICAgICB9CisgICAgICAgIHJldHVybiAwOworICAgIH0KKyAgICAKICAg ICBzaXplX3QgYml0Q291bnQoKSBjb25zdAogICAgIHsKICAgICAgICAgc2l6ZV90IHJlc3VsdCA9 IDA7CkluZGV4OiBTb3VyY2UvV1RGL3d0Zi9QYXJraW5nTG90LmNwcAo9PT09PT09PT09PT09PT09 PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci0tLSBT b3VyY2UvV1RGL3d0Zi9QYXJraW5nTG90LmNwcAkocmV2aXNpb24gMjAzNDczKQorKysgU291cmNl L1dURi93dGYvUGFya2luZ0xvdC5jcHAJKHdvcmtpbmcgY29weSkKQEAgLTI4LDYgKzI4LDcgQEAK IAogI2luY2x1ZGUgIkN1cnJlbnRUaW1lLmgiCiAjaW5jbHVkZSAiRGF0YUxvZy5oIgorI2luY2x1 ZGUgIkZhc3RCaXRWZWN0b3IuaCIKICNpbmNsdWRlICJIYXNoRnVuY3Rpb25zLmgiCiAjaW5jbHVk ZSAiU3RyaW5nUHJpbnRTdHJlYW0uaCIKICNpbmNsdWRlICJUaHJlYWRTcGVjaWZpYy5oIgpAQCAt NTksOCArNjAsNiBAQCBwdWJsaWM6CiAKICAgICBjb25zdCB2b2lkKiBhZGRyZXNzIHsgbnVsbHB0 ciB9OwogICAgIAotICAgIFRocmVhZERhdGEqIG5leHRJblF1ZXVlIHsgbnVsbHB0ciB9OwotICAg IAogICAgIGludHB0cl90IHRva2VuIHsgMCB9OwogfTsKIApAQCAtNzYsNiArNzUsOCBAQCBwdWJs aWM6CiAgICAgQnVja2V0KCkKICAgICAgICAgOiByYW5kb20oc3RhdGljX2Nhc3Q8dW5zaWduZWQ+ KGJpdHdpc2VfY2FzdDxpbnRwdHJfdD4odGhpcykpKSAvLyBDYW5ub3QgdXNlIGRlZmF1bHQgc2Vl ZCBzaW5jZSB0aGF0IHJlY3Vyc2VzIGludG8gTG9jay4KICAgICB7CisgICAgICAgIGJpdFZlY3Rv ci5yZXNpemUoMzIpOyAvLyBzdGFydCB3aXRoIGp1c3QgMSB1aW50MzJfdAorICAgICAgICBxdWV1 ZUhlYWQgPSBzdGF0aWNfY2FzdDxUaHJlYWREYXRhKio+KGZhc3RaZXJvZWRNYWxsb2Moc2l6ZW9m KFRocmVhZERhdGEqKSAqIGJpdFZlY3Rvci5udW1CaXRzKCkpKTsKICAgICB9CiAgICAgCiAgICAg dm9pZCBlbnF1ZXVlKFRocmVhZERhdGEqIGRhdGEpCkBAIC04MywxNiArODQsMzEgQEAgcHVibGlj OgogICAgICAgICBpZiAodmVyYm9zZSkKICAgICAgICAgICAgIGRhdGFMb2codG9TdHJpbmcoY3Vy cmVudFRocmVhZCgpLCAiOiBlbnF1ZXVlaW5nICIsIFJhd1BvaW50ZXIoZGF0YSksICIgd2l0aCBh ZGRyZXNzID0gIiwgUmF3UG9pbnRlcihkYXRhLT5hZGRyZXNzKSwgIiBvbnRvICIsIFJhd1BvaW50 ZXIodGhpcyksICJcbiIpKTsKICAgICAgICAgQVNTRVJUKGRhdGEtPmFkZHJlc3MpOwotICAgICAg ICBBU1NFUlQoIWRhdGEtPm5leHRJblF1ZXVlKTsKICAgICAgICAgCi0gICAgICAgIGlmIChxdWV1 ZVRhaWwpIHsKLSAgICAgICAgICAgIHF1ZXVlVGFpbC0+bmV4dEluUXVldWUgPSBkYXRhOwotICAg ICAgICAgICAgcXVldWVUYWlsID0gZGF0YTsKLSAgICAgICAgICAgIHJldHVybjsKKyAgICAgICAg c2l6ZV90IGluZGV4ID0gYml0VmVjdG9yLmZmeigpOworICAgICAgICAvLyB1bmxpa2VseSBhcyAz MiB0aHJlYWRzIHdhaXRpbmcgb24gc2FtZSBhZGRyZXNzIHByb2JhYmx5IGluZGljYXRlIGJhZCBk ZXNpZ24KKyAgICAgICAgLy8gb3IgMzIgYWRkcmVzc2VzIGhhc2hpbmcgdG8gc2FtZSBidWNrZXQK KyAgICAgICAgaWYgKCFpbmRleCkgeworICAgICAgICAgICAgcmVzaXplKCk7CisgICAgICAgICAg ICBpbmRleCA9IGJpdFZlY3Rvci5mZnooKTsKICAgICAgICAgfQotCi0gICAgICAgIHF1ZXVlSGVh ZCA9IGRhdGE7Ci0gICAgICAgIHF1ZXVlVGFpbCA9IGRhdGE7CisgICAgICAgIGJpdFZlY3Rvci5z ZXQoaW5kZXggLSAxKTsKKyAgICAgICAgcXVldWVIZWFkW2luZGV4IC0gMV0gPSBkYXRhOworICAg IH0KKyAgICAKKyAgICB2b2lkIHJlc2l6ZSgpCisgICAgeworICAgICAgICBzaXplX3Qgb2xkU2l6 ZSA9IGJpdFZlY3Rvci5udW1CaXRzKCk7CisgICAgICAgIAorICAgICAgICAvLyBpbmNyZWFzZSBz aXplIGJ5IDIgdGltZXMuCisgICAgICAgIGJpdFZlY3Rvci5yZXNpemUob2xkU2l6ZSA8PCAxKTsK KyAgICAgICAgCisgICAgICAgIFRocmVhZERhdGEqKiBuZXdRdWV1ZUhlYWQgPSBzdGF0aWNfY2Fz dDxUaHJlYWREYXRhKio+KGZhc3RaZXJvZWRNYWxsb2Moc2l6ZW9mKFRocmVhZERhdGEqKSAqIGJp dFZlY3Rvci5udW1CaXRzKCkpKTsKKyAgICAgICAgLy8gTm90IHZlcnkgZWZmaWNpZW50LCBidXQg cmVzaXplKCkgc2hvdWxkIGhhcHBlbiByYXJlbHkKKyAgICAgICAgZm9yIChzaXplX3QgaSA9IDA7 IGkgPCBvbGRTaXplIDsgaSsrKQorICAgICAgICAgICAgbmV3UXVldWVIZWFkW2ldID0gcXVldWVI ZWFkW2ldOworICAgICAgICAKKyAgICAgICAgcXVldWVIZWFkID0gbmV3UXVldWVIZWFkOwogICAg IH0KIAogICAgIHRlbXBsYXRlPHR5cGVuYW1lIEZ1bmN0b3I+CkBAIC0xMDEsMzcgKzExNyw3IEBA IHB1YmxpYzoKICAgICAgICAgaWYgKHZlcmJvc2UpCiAgICAgICAgICAgICBkYXRhTG9nKHRvU3Ry aW5nKGN1cnJlbnRUaHJlYWQoKSwgIjogZGVxdWV1ZWluZyBmcm9tIGJ1Y2tldCBhdCAiLCBSYXdQ b2ludGVyKHRoaXMpLCAiXG4iKSk7CiAgICAgICAgIAotICAgICAgICBpZiAoIXF1ZXVlSGVhZCkg ewotICAgICAgICAgICAgaWYgKHZlcmJvc2UpCi0gICAgICAgICAgICAgICAgZGF0YUxvZyh0b1N0 cmluZyhjdXJyZW50VGhyZWFkKCksICI6IGVtcHR5LlxuIikpOwotICAgICAgICAgICAgcmV0dXJu OwotICAgICAgICB9Ci0KLSAgICAgICAgLy8gVGhpcyBsb29wIGlzIGEgdmVyeSBjbGV2ZXIgYWJv bWluYXRpb24uIFRoZSBpbmR1Y3Rpb24gdmFyaWFibGVzIGFyZSB0aGUgcG9pbnRlciB0byB0aGUK LSAgICAgICAgLy8gcG9pbnRlciB0byB0aGUgY3VycmVudCBub2RlLCBhbmQgdGhlIHBvaW50ZXIg dG8gdGhlIHByZXZpb3VzIG5vZGUuIFRoaXMgZ2l2ZXMgdXMgZXZlcnl0aGluZwotICAgICAgICAv LyB3ZSBuZWVkIHRvIGJvdGggcHJvY2VlZCBmb3J3YXJkIHRvIHRoZSBuZXh0IG5vZGUsIGFuZCB0 byByZW1vdmUgbm9kZXMgd2hpbGUgbWFpbnRhaW5pbmcgdGhlCi0gICAgICAgIC8vIHF1ZXVlSGVh ZC9xdWV1ZVRhaWwgYW5kIGFsbCBvZiB0aGUgbmV4dEluUXVldWUgbGlua3MuIEZvciBleGFtcGxl LCB3aGVuIHdlIGFyZSBhdCB0aGUgaGVhZAotICAgICAgICAvLyBlbGVtZW50LCB0aGVuIHJlbW92 YWwgbWVhbnMgcmV3aXJpbmcgcXVldWVIZWFkLCBhbmQgaWYgaXQgd2FzIGFsc28gZXF1YWwgdG8g cXVldWVUYWlsLCB0aGVuCi0gICAgICAgIC8vIHdlJ2Qgd2FudCBxdWV1ZVRhaWwgdG8gYmUgc2V0 IHRvIG51bGxwdHIuIFRoaXMgd29ya3MgYmVjYXVzZToKLSAgICAgICAgLy8KLSAgICAgICAgLy8g ICAgIGN1cnJlbnRQdHIgPT0gJnF1ZXVlSGVhZAotICAgICAgICAvLyAgICAgcHJldmlvdXMgPT0g bnVsbHB0cgotICAgICAgICAvLwotICAgICAgICAvLyBXZSByZW1vdmUgYnkgc2V0dGluZyAqY3Vy cmVudFB0ciA9ICgqY3VycmVudFB0ciktPm5leHRJblF1ZXVlLCBpLmUuIGNoYW5naW5nIHRoZSBw b2ludGVyCi0gICAgICAgIC8vIHRoYXQgdXNlZCB0byBwb2ludCB0byB0aGlzIG5vZGUgdG8gaW5z dGVhZCBwb2ludCB0byB0aGlzIG5vZGUncyBzdWNjZXNzb3IuIEFub3RoZXIgZXhhbXBsZToKLSAg ICAgICAgLy8gaWYgd2Ugd2VyZSBhdCB0aGUgc2Vjb25kIG5vZGUgaW4gdGhlIHF1ZXVlLCB0aGVu IHdlJ2QgaGF2ZToKLSAgICAgICAgLy8KLSAgICAgICAgLy8gICAgIGN1cnJlbnRQdHIgPT0gJnF1 ZXVlSGVhZC0+bmV4dEluUXVldWUKLSAgICAgICAgLy8gICAgIHByZXZpb3VzID09IHF1ZXVlSGVh ZAotICAgICAgICAvLwotICAgICAgICAvLyBJZiB0aGlzIG5vZGUgaXMgbm90IGVxdWFsIHRvIHF1 ZXVlVGFpbCwgdGhlbiByZW1vdmluZyBpdCBzaW1wbHkgbWVhbnMgbWFraW5nCi0gICAgICAgIC8v IHF1ZXVlSGVhZC0+bmV4dEluUXVldWUgcG9pbnQgdG8gcXVldWVIZWFkLT5uZXh0SW5RdWV1ZS0+ bmV4dEluUXVldWUgKHdoaWNoIHRoZSBhbGdvcml0aG0KLSAgICAgICAgLy8gYWNoaWV2ZXMgYnkg bXV0YXRpbmcgKmN1cnJlbnRQdHIpLiBJZiB0aGlzIG5vZGUgaXMgZXF1YWwgdG8gcXVldWVUYWls LCB0aGVuIHdlIHdhbnQgdG8gc2V0Ci0gICAgICAgIC8vIHF1ZXVlVGFpbCB0byBwcmV2aW91cywg d2hpY2ggaW4gdGhpcyBjYXNlIGlzIHF1ZXVlSGVhZCAtIHRodXMgbWFraW5nIHRoZSBxdWV1ZSBs b29rIGxpa2UgYQotICAgICAgICAvLyBwcm9wZXIgb25lLWVsZW1lbnQgcXVldWUgd2l0aCBxdWV1 ZUhlYWQgPT0gcXVldWVUYWlsLgogICAgICAgICBib29sIHNob3VsZENvbnRpbnVlID0gdHJ1ZTsK LSAgICAgICAgVGhyZWFkRGF0YSoqIGN1cnJlbnRQdHIgPSAmcXVldWVIZWFkOwotICAgICAgICBU aHJlYWREYXRhKiBwcmV2aW91cyA9IG51bGxwdHI7CiAKICAgICAgICAgZG91YmxlIHRpbWUgPSBt b25vdG9uaWNhbGx5SW5jcmVhc2luZ1RpbWVNUygpOwogICAgICAgICBib29sIHRpbWVUb0JlRmFp ciA9IGZhbHNlOwpAQCAtMTQwLDE5ICsxMjYsMTMgQEAgcHVibGljOgogICAgICAgICAKICAgICAg ICAgYm9vbCBkaWREZXF1ZXVlID0gZmFsc2U7CiAgICAgICAgIAotICAgICAgICB3aGlsZSAoc2hv dWxkQ29udGludWUpIHsKLSAgICAgICAgICAgIFRocmVhZERhdGEqIGN1cnJlbnQgPSAqY3VycmVu dFB0cjsKKyAgICAgICAgZm9yIChzaXplX3QgY3VycmVudEluZGV4ID0gYml0VmVjdG9yLmZmcygp IDsgc2hvdWxkQ29udGludWUgJiYgY3VycmVudEluZGV4IDsgY3VycmVudEluZGV4ID0gYml0VmVj dG9yLmZmcyhjdXJyZW50SW5kZXgpKSB7CisgICAgICAgICAgICBUaHJlYWREYXRhKiBjdXJyZW50 ID0gcXVldWVIZWFkW2N1cnJlbnRJbmRleCAtIDFdOwogICAgICAgICAgICAgaWYgKHZlcmJvc2Up CiAgICAgICAgICAgICAgICAgZGF0YUxvZyh0b1N0cmluZyhjdXJyZW50VGhyZWFkKCksICI6IGdv dCB0aHJlYWQgIiwgUmF3UG9pbnRlcihjdXJyZW50KSwgIlxuIikpOwotICAgICAgICAgICAgaWYg KCFjdXJyZW50KQotICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgRGVxdWV1ZVJl c3VsdCByZXN1bHQgPSBmdW5jdG9yKGN1cnJlbnQsIHRpbWVUb0JlRmFpcik7CiAgICAgICAgICAg ICBzd2l0Y2ggKHJlc3VsdCkgewogICAgICAgICAgICAgY2FzZSBEZXF1ZXVlUmVzdWx0OjpJZ25v cmU6Ci0gICAgICAgICAgICAgICAgaWYgKHZlcmJvc2UpCi0gICAgICAgICAgICAgICAgICAgIGRh dGFMb2codG9TdHJpbmcoY3VycmVudFRocmVhZCgpLCAiOiBjdXJyZW50UHRyID0gIiwgUmF3UG9p bnRlcihjdXJyZW50UHRyKSwgIiwgKmN1cnJlbnRQdHIgPSAiLCBSYXdQb2ludGVyKCpjdXJyZW50 UHRyKSwgIlxuIikpOwotICAgICAgICAgICAgICAgIHByZXZpb3VzID0gY3VycmVudDsKLSAgICAg ICAgICAgICAgICBjdXJyZW50UHRyID0gJigqY3VycmVudFB0ciktPm5leHRJblF1ZXVlOwogICAg ICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgY2FzZSBEZXF1ZXVlUmVzdWx0OjpSZW1v dmVBbmRTdG9wOgogICAgICAgICAgICAgICAgIHNob3VsZENvbnRpbnVlID0gZmFsc2U7CkBAIC0x NjAsMTkgKzE0MCwxNiBAQCBwdWJsaWM6CiAgICAgICAgICAgICBjYXNlIERlcXVldWVSZXN1bHQ6 OlJlbW92ZUFuZENvbnRpbnVlOgogICAgICAgICAgICAgICAgIGlmICh2ZXJib3NlKQogICAgICAg ICAgICAgICAgICAgICBkYXRhTG9nKHRvU3RyaW5nKGN1cnJlbnRUaHJlYWQoKSwgIjogZGVxdWV1 ZWluZyAiLCBSYXdQb2ludGVyKGN1cnJlbnQpLCAiIGZyb20gIiwgUmF3UG9pbnRlcih0aGlzKSwg IlxuIikpOwotICAgICAgICAgICAgICAgIGlmIChjdXJyZW50ID09IHF1ZXVlVGFpbCkKLSAgICAg ICAgICAgICAgICAgICAgcXVldWVUYWlsID0gcHJldmlvdXM7CiAgICAgICAgICAgICAgICAgZGlk RGVxdWV1ZSA9IHRydWU7Ci0gICAgICAgICAgICAgICAgKmN1cnJlbnRQdHIgPSBjdXJyZW50LT5u ZXh0SW5RdWV1ZTsKLSAgICAgICAgICAgICAgICBjdXJyZW50LT5uZXh0SW5RdWV1ZSA9IG51bGxw dHI7CisgICAgICAgICAgICAgICAgYml0VmVjdG9yLmNsZWFyKGN1cnJlbnRJbmRleCAtIDEpOwog ICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgfQorICAgICAgICAgICAgaWYgKCFz aG91bGRDb250aW51ZSkKKyAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgfQogICAgICAg ICAKICAgICAgICAgaWYgKHRpbWVUb0JlRmFpciAmJiBkaWREZXF1ZXVlKQogICAgICAgICAgICAg bmV4dEZhaXJUaW1lID0gdGltZSArIHJhbmRvbS5nZXQoKTsKLQotICAgICAgICBBU1NFUlQoISFx dWV1ZUhlYWQgPT0gISFxdWV1ZVRhaWwpOwogICAgIH0KICAgICAKICAgICBUaHJlYWREYXRhKiBk ZXF1ZXVlKCkKQEAgLTE4Niw5ICsxNjMsNiBAQCBwdWJsaWM6CiAgICAgICAgIHJldHVybiByZXN1 bHQ7CiAgICAgfQogCi0gICAgVGhyZWFkRGF0YSogcXVldWVIZWFkIHsgbnVsbHB0ciB9OwotICAg IFRocmVhZERhdGEqIHF1ZXVlVGFpbCB7IG51bGxwdHIgfTsKLQogICAgIC8vIFRoaXMgbG9jayBw cm90ZWN0cyB0aGUgZW50aXJlIGJ1Y2tldC4gVGhvdSBzaGFsbCBub3QgbWFrZSBjaGFuZ2VzIHRv IEJ1Y2tldCB3aXRob3V0IGhvbGRpbmcKICAgICAvLyB0aGlzIGxvY2suCiAgICAgV29yZExvY2sg bG9jazsKQEAgLTE5Nyw2ICsxNzEsMTIgQEAgcHVibGljOgogICAgIAogICAgIFdlYWtSYW5kb20g cmFuZG9tOwogCisgICAgVGhyZWFkRGF0YSoqIHF1ZXVlSGVhZCB7IG51bGxwdHIgfTsKKyAgICAK KyAgICAvLyBiaXQgdmVjdG9yIHRvIGluZGljYXRlIGlmIGJ1Y2tldCBzbG90IGlzIGZyZWUgb3Ig b2NjdXBpZWQKKyAgICAvLyAwIGluZGljYXRlIGZyZWUgYW5kIDEgaXMgb2NjdXBpZWQKKyAgICBG YXN0Qml0VmVjdG9yIGJpdFZlY3RvcjsKKwogICAgIC8vIFB1dCBzb21lIGRpc3RhbmUgYmV0d2Vl biBidWNrZXRzIGluIG1lbW9yeS4gVGhpcyBpcyBvbmUgb2Ygc2V2ZXJhbCBtaXRpZ2F0aW9ucyBh Z2FpbnN0IGZhbHNlCiAgICAgLy8gc2hhcmluZy4KICAgICBjaGFyIHBhZGRpbmdbNjRdOwpAQCAt NTQ2LDcgKzUyNiw3IEBAIGJvb2wgZGVxdWV1ZSgKICAgICAgICAgfQogCiAgICAgICAgIGJ1Y2tl dC0+Z2VuZXJpY0RlcXVldWUoZGVxdWV1ZUZ1bmN0b3IpOwotICAgICAgICBib29sIHJlc3VsdCA9 ICEhYnVja2V0LT5xdWV1ZUhlYWQ7CisgICAgICAgIGJvb2wgcmVzdWx0ID0gISFidWNrZXQtPmJp dFZlY3Rvci5mZnMoKTsKICAgICAgICAgZmluaXNoRnVuY3RvcihyZXN1bHQpOwogICAgICAgICBi dWNrZXQtPmxvY2sudW5sb2NrKCk7CiAgICAgICAgIHJldHVybiByZXN1bHQ7CkBAIC02MzEsNyAr NjExLDYgQEAgTkVWRVJfSU5MSU5FIFBhcmtpbmdMb3Q6OlBhcmtSZXN1bHQgUGFyawogICAgIC8v IElmIGRpZERlcXVldWUgaXMgdHJ1ZSwgdGhlbiB3ZSBkZXF1ZXVlZCBvdXJzZWx2ZXMuIFRoaXMg bWVhbnMgdGhhdCB3ZSB3ZXJlIG5vdCB1bnBhcmtlZC4KICAgICAvLyBJZiBkaWREZXF1ZXVlIGlz IGZhbHNlLCB0aGVuIHNvbWVvbmUgdW5wYXJrZWQgdXMuCiAgICAgCi0gICAgUkVMRUFTRV9BU1NF UlQoIW1lLT5uZXh0SW5RdWV1ZSk7CiAKICAgICAvLyBNYWtlIHN1cmUgdGhhdCBubyBtYXR0ZXIg d2hhdCwgbWUtPmFkZHJlc3MgaXMgbnVsbCBhZnRlciB0aGlzIHBvaW50LgogICAgIHsKQEAgLTc3 Niw4ICs3NTUsMTAgQEAgTkVWRVJfSU5MSU5FIHZvaWQgUGFya2luZ0xvdDo6Zm9yRWFjaChzdAog ICAgICAgICBCdWNrZXQqIGJ1Y2tldCA9IGN1cnJlbnRIYXNodGFibGUtPmRhdGFbaV0ubG9hZCgp OwogICAgICAgICBpZiAoIWJ1Y2tldCkKICAgICAgICAgICAgIGNvbnRpbnVlOwotICAgICAgICBm b3IgKFRocmVhZERhdGEqIGN1cnJlbnRUaHJlYWREYXRhID0gYnVja2V0LT5xdWV1ZUhlYWQ7IGN1 cnJlbnRUaHJlYWREYXRhOyBjdXJyZW50VGhyZWFkRGF0YSA9IGN1cnJlbnRUaHJlYWREYXRhLT5u ZXh0SW5RdWV1ZSkKKyAgICAgICAgZm9yIChzaXplX3QgY3VycmVudEluZGV4ID0gYnVja2V0LT5i aXRWZWN0b3IuZmZzKCkgOyBjdXJyZW50SW5kZXggOyBjdXJyZW50SW5kZXggPSBidWNrZXQtPmJp dFZlY3Rvci5mZnMoY3VycmVudEluZGV4KSkgeworICAgICAgICAgICAgVGhyZWFkRGF0YSogY3Vy cmVudFRocmVhZERhdGEgPSBidWNrZXQtPnF1ZXVlSGVhZFtjdXJyZW50SW5kZXggLSAxXTsKICAg ICAgICAgICAgIGNhbGxiYWNrKGN1cnJlbnRUaHJlYWREYXRhLT50aHJlYWRJZGVudGlmaWVyLCBj dXJyZW50VGhyZWFkRGF0YS0+YWRkcmVzcyk7CisgICAgICAgIH0KICAgICB9CiAgICAgCiAgICAg dW5sb2NrSGFzaHRhYmxlKGJ1Y2tldHNUb1VubG9jayk7Cg==