Implement timeline fences in Dawn

This change implements timeline fences in Dawn.
It includes methods and descriptor members to eventually
support multi-queue, but does not implement them.

Bug: dawn:26
Change-Id: I81d5fee6acef402fe099227a034d9669a89ab6c3
Reviewed-on: https://dawn-review.googlesource.com/c/2460
Commit-Queue: Austin Eng <enga@chromium.org>
Reviewed-by: Kai Ninomiya <kainino@chromium.org>
diff --git a/BUILD.gn b/BUILD.gn
index 869c332..777ebb9 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -390,6 +390,10 @@
     "src/dawn_native/Error.h",
     "src/dawn_native/ErrorData.cpp",
     "src/dawn_native/ErrorData.h",
+    "src/dawn_native/Fence.cpp",
+    "src/dawn_native/Fence.h",
+    "src/dawn_native/FenceSignalTracker.cpp",
+    "src/dawn_native/FenceSignalTracker.h",
     "src/dawn_native/Forward.h",
     "src/dawn_native/InputState.cpp",
     "src/dawn_native/InputState.h",
@@ -828,6 +832,7 @@
     "src/tests/unittests/validation/CopyCommandsValidationTests.cpp",
     "src/tests/unittests/validation/DepthStencilStateValidationTests.cpp",
     "src/tests/unittests/validation/DynamicStateCommandValidationTests.cpp",
+    "src/tests/unittests/validation/FenceValidationTests.cpp",
     "src/tests/unittests/validation/InputStateValidationTests.cpp",
     "src/tests/unittests/validation/PushConstantsValidationTests.cpp",
     "src/tests/unittests/validation/QueueSubmitValidationTests.cpp",
@@ -877,6 +882,7 @@
     "src/tests/end2end/CopyTests.cpp",
     "src/tests/end2end/DepthStencilStateTests.cpp",
     "src/tests/end2end/DrawElementsTests.cpp",
+    "src/tests/end2end/FenceTests.cpp",
     "src/tests/end2end/IndexFormatTests.cpp",
     "src/tests/end2end/InputStateTests.cpp",
     "src/tests/end2end/PrimitiveTopologyTests.cpp",
diff --git a/dawn.json b/dawn.json
index b43a7fe..7f6a255 100644
--- a/dawn.json
+++ b/dawn.json
@@ -482,6 +482,13 @@
                 "returns": "depth stencil state builder"
             },
             {
+                "name": "create fence",
+                "returns": "fence",
+                "args": [
+                    {"name": "descriptor", "type": "fence descriptor", "annotation": "const*"}
+                ]
+            },
+            {
                 "name": "create render pass descriptor builder",
                 "returns": "render pass descriptor builder"
             },
@@ -609,6 +616,42 @@
             {"value": 3, "name": "both"}
         ]
     },
+    "fence": {
+        "category": "object",
+        "methods": [
+            {
+                "name": "get completed value",
+                "returns": "uint64_t"
+            },
+            {
+                "name": "on completion",
+                "args": [
+                    {"name": "value", "type": "uint64_t"},
+                    {"name": "callback", "type": "fence on completion callback"},
+                    {"name": "userdata", "type": "callback userdata"}
+                ]
+            }
+        ]
+    },
+    "fence on completion callback": {
+        "category": "natively defined"
+    },
+    "fence completion status": {
+        "category": "enum",
+        "values": [
+            {"value": 0, "name": "success"},
+            {"value": 1, "name": "error"},
+            {"value": 2, "name": "unknown"},
+            {"value": 3, "name": "context lost"}
+        ]
+    },
+    "fence descriptor": {
+        "category": "structure",
+        "extensible": true,
+        "members": [
+            {"name": "initial value", "type": "uint64_t"}
+        ]
+    },
     "filter mode": {
         "category": "enum",
         "values": [
@@ -707,6 +750,13 @@
                     {"name": "num commands", "type": "uint32_t"},
                     {"name": "commands", "type": "command buffer", "annotation": "const*", "length": "num commands"}
                 ]
+            },
+            {
+                "name": "signal",
+                "args": [
+                    {"name": "fence", "type": "fence"},
+                    {"name": "signal value", "type": "uint64_t"}
+                ]
             }
         ]
     },
diff --git a/generator/templates/api.h b/generator/templates/api.h
index 0b8a19a..d4aedd7 100644
--- a/generator/templates/api.h
+++ b/generator/templates/api.h
@@ -53,6 +53,8 @@
 typedef void (*dawnBuilderErrorCallback)(dawnBuilderErrorStatus status, const char* message, dawnCallbackUserdata userdata1, dawnCallbackUserdata userdata2);
 typedef void (*dawnBufferMapReadCallback)(dawnBufferMapAsyncStatus status, const void* data, dawnCallbackUserdata userdata);
 typedef void (*dawnBufferMapWriteCallback)(dawnBufferMapAsyncStatus status, void* data, dawnCallbackUserdata userdata);
+typedef void (*dawnFenceOnCompletionCallback)(dawnFenceCompletionStatus status,
+                                              dawnCallbackUserdata userdata);
 
 #ifdef __cplusplus
 extern "C" {
diff --git a/generator/templates/dawn_wire/WireClient.cpp b/generator/templates/dawn_wire/WireClient.cpp
index 117cfad..ba74c66 100644
--- a/generator/templates/dawn_wire/WireClient.cpp
+++ b/generator/templates/dawn_wire/WireClient.cpp
@@ -16,6 +16,7 @@
 #include "dawn_wire/WireCmd.h"
 
 #include "common/Assert.h"
+#include "common/SerialMap.h"
 
 #include <cstring>
 #include <cstdlib>
@@ -68,6 +69,7 @@
         {% set special_objects = [
             "device",
             "buffer",
+            "fence",
         ] %}
         {% for type in by_category["object"] if not type.name.canonical_case() in special_objects %}
             struct {{type.name.CamelCase()}} : ObjectBase {
@@ -118,6 +120,35 @@
             bool isWriteMapped = false;
         };
 
+        struct Fence : ObjectBase {
+            using ObjectBase::ObjectBase;
+
+            ~Fence() {
+                //* Callbacks need to be fired in all cases, as they can handle freeing resources
+                //* so we call them with "Unknown" status.
+                for (auto& request : requests.IterateAll()) {
+                    request.completionCallback(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, request.userdata);
+                }
+                requests.Clear();
+            }
+
+            void CheckPassedFences() {
+                for (auto& request : requests.IterateUpTo(completedValue)) {
+                    request.completionCallback(DAWN_FENCE_COMPLETION_STATUS_SUCCESS,
+                                               request.userdata);
+                }
+                requests.ClearUpTo(completedValue);
+            }
+
+            struct OnCompletionData {
+                dawnFenceOnCompletionCallback completionCallback = nullptr;
+                dawnCallbackUserdata userdata = 0;
+            };
+            uint64_t signaledValue = 0;
+            uint64_t completedValue = 0;
+            SerialMap<OnCompletionData> requests;
+        };
+
         //* TODO(cwallez@chromium.org): Do something with objects before they are destroyed ?
         //*  - Call still uncalled builder callbacks
         template<typename T>
@@ -238,6 +269,8 @@
                CommandSerializer* mSerializer = nullptr;
         };
 
+        {% set client_side_commands = ["FenceGetCompletedValue"] %}
+
         //* Implementation of the client API functions.
         {% for type in by_category["object"] %}
             {% set Type = type.name.CamelCase() %}
@@ -245,50 +278,51 @@
 
             {% for method in type.methods %}
                 {% set Suffix = as_MethodSuffix(type.name, method.name) %}
+                {% if Suffix not in client_side_commands %}
+                    {{as_cType(method.return_type.name)}} Client{{Suffix}}(
+                        {{-cType}} cSelf
+                        {%- for arg in method.arguments -%}
+                            , {{as_annotated_cType(arg)}}
+                        {%- endfor -%}
+                    ) {
+                        auto self = reinterpret_cast<{{as_wireType(type)}}>(cSelf);
+                        Device* device = self->device;
+                        {{Suffix}}Cmd cmd;
 
-                {{as_cType(method.return_type.name)}} Client{{Suffix}}(
-                    {{-cType}} cSelf
-                    {%- for arg in method.arguments -%}
-                        , {{as_annotated_cType(arg)}}
-                    {%- endfor -%}
-                ) {
-                    auto self = reinterpret_cast<{{as_wireType(type)}}>(cSelf);
-                    Device* device = self->device;
-                    {{Suffix}}Cmd cmd;
+                        //* Create the structure going on the wire on the stack and fill it with the value
+                        //* arguments so it can compute its size.
+                        cmd.self = cSelf;
 
-                    //* Create the structure going on the wire on the stack and fill it with the value
-                    //* arguments so it can compute its size.
-                    cmd.self = cSelf;
+                        //* For object creation, store the object ID the client will use for the result.
+                        {% if method.return_type.category == "object" %}
+                            auto* allocation = self->device->{{method.return_type.name.camelCase()}}.New();
 
-                    //* For object creation, store the object ID the client will use for the result.
-                    {% if method.return_type.category == "object" %}
-                        auto* allocation = self->device->{{method.return_type.name.camelCase()}}.New();
+                            {% if type.is_builder %}
+                                //* We are in GetResult, so the callback that should be called is the
+                                //* currently set one. Copy it over to the created object and prevent the
+                                //* builder from calling the callback on destruction.
+                                allocation->object->builderCallback = self->builderCallback;
+                                self->builderCallback.canCall = false;
+                            {% endif %}
 
-                        {% if type.is_builder %}
-                            //* We are in GetResult, so the callback that should be called is the
-                            //* currently set one. Copy it over to the created object and prevent the
-                            //* builder from calling the callback on destruction.
-                            allocation->object->builderCallback = self->builderCallback;
-                            self->builderCallback.canCall = false;
+                            cmd.resultId = allocation->object->id;
+                            cmd.resultSerial = allocation->serial;
                         {% endif %}
 
-                        cmd.resultId = allocation->object->id;
-                        cmd.resultSerial = allocation->serial;
-                    {% endif %}
+                        {% for arg in method.arguments %}
+                            cmd.{{as_varName(arg.name)}} = {{as_varName(arg.name)}};
+                        {% endfor %}
 
-                    {% for arg in method.arguments %}
-                        cmd.{{as_varName(arg.name)}} = {{as_varName(arg.name)}};
-                    {% endfor %}
+                        //* Allocate space to send the command and copy the value args over.
+                        size_t requiredSize = cmd.GetRequiredSize();
+                        char* allocatedBuffer = static_cast<char*>(device->GetCmdSpace(requiredSize));
+                        cmd.Serialize(allocatedBuffer, *device);
 
-                    //* Allocate space to send the command and copy the value args over.
-                    size_t requiredSize = cmd.GetRequiredSize();
-                    char* allocatedBuffer = static_cast<char*>(device->GetCmdSpace(requiredSize));
-                    cmd.Serialize(allocatedBuffer, *device);
-
-                    {% if method.return_type.category == "object" %}
-                        return reinterpret_cast<{{as_cType(method.return_type.name)}}>(allocation->object.get());
-                    {% endif %}
-                }
+                        {% if method.return_type.category == "object" %}
+                            return reinterpret_cast<{{as_cType(method.return_type.name)}}>(allocation->object.get());
+                        {% endif %}
+                    }
+                {% endif %}
             {% endfor %}
 
             {% if type.is_builder %}
@@ -379,6 +413,33 @@
             *allocCmd = cmd;
         }
 
+        uint64_t ClientFenceGetCompletedValue(dawnFence cSelf) {
+            auto fence = reinterpret_cast<Fence*>(cSelf);
+            return fence->completedValue;
+        }
+
+        void ClientFenceOnCompletion(dawnFence cFence,
+                                     uint64_t value,
+                                     dawnFenceOnCompletionCallback callback,
+                                     dawnCallbackUserdata userdata) {
+            Fence* fence = reinterpret_cast<Fence*>(cFence);
+            if (value > fence->signaledValue) {
+                fence->device->HandleError("Value greater than fence signaled value");
+                callback(DAWN_FENCE_COMPLETION_STATUS_ERROR, userdata);
+                return;
+            }
+
+            if (value <= fence->completedValue) {
+                callback(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata);
+                return;
+            }
+
+            Fence::OnCompletionData request;
+            request.completionCallback = callback;
+            request.userdata = userdata;
+            fence->requests.Enqueue(std::move(request), value);
+        }
+
         void ProxyClientBufferUnmap(dawnBuffer cBuffer) {
             Buffer* buffer = reinterpret_cast<Buffer*>(cBuffer);
 
@@ -412,6 +473,25 @@
             ClientBufferUnmap(cBuffer);
         }
 
+        dawnFence ProxyClientDeviceCreateFence(dawnDevice cSelf,
+                                               dawnFenceDescriptor const* descriptor) {
+            dawnFence cFence = ClientDeviceCreateFence(cSelf, descriptor);
+            Fence* fence = reinterpret_cast<Fence*>(cFence);
+            fence->signaledValue = descriptor->initialValue;
+            fence->completedValue = descriptor->initialValue;
+            return cFence;
+        }
+
+        void ProxyClientQueueSignal(dawnQueue cQueue, dawnFence cFence, uint64_t signalValue) {
+            Fence* fence = reinterpret_cast<Fence*>(cFence);
+            if (signalValue <= fence->signaledValue) {
+                fence->device->HandleError("Fence value less than or equal to signaled value");
+                return;
+            }
+            fence->signaledValue = signalValue;
+            ClientQueueSignal(cQueue, cFence, signalValue);
+        }
+
         void ClientDeviceReference(dawnDevice) {
         }
 
@@ -429,7 +509,7 @@
         //  - An autogenerated Client{{suffix}} method that sends the command on the wire
         //  - A manual ProxyClient{{suffix}} method that will be inserted in the proctable instead of
         //    the autogenerated one, and that will have to call Client{{suffix}}
-        {% set proxied_commands = ["BufferUnmap"] %}
+        {% set proxied_commands = ["BufferUnmap", "DeviceCreateFence", "QueueSignal"] %}
 
         dawnProcTable GetProcs() {
             dawnProcTable table;
@@ -471,6 +551,9 @@
                             case ReturnWireCmd::BufferMapWriteAsyncCallback:
                                 success = HandleBufferMapWriteAsyncCallback(&commands, &size);
                                 break;
+                            case ReturnWireCmd::FenceUpdateCompletedValue:
+                                success = HandleFenceUpdateCompletedValue(&commands, &size);
+                                break;
                             default:
                                 success = false;
                         }
@@ -675,6 +758,25 @@
 
                     return true;
                 }
+
+                bool HandleFenceUpdateCompletedValue(const char** commands, size_t* size) {
+                    const auto* cmd = GetCommand<ReturnFenceUpdateCompletedValueCmd>(commands, size);
+                    if (cmd == nullptr) {
+                        return false;
+                    }
+
+                    auto* fence = mDevice->fence.GetObject(cmd->fenceId);
+                    uint32_t fenceSerial = mDevice->fence.GetSerial(cmd->fenceId);
+
+                    //* The fence might have been deleted or recreated so this isn't an error.
+                    if (fence == nullptr || fenceSerial != cmd->fenceSerial) {
+                        return true;
+                    }
+
+                    fence->completedValue = cmd->value;
+                    fence->CheckPassedFences();
+                    return true;
+                }
         };
 
     }
diff --git a/generator/templates/dawn_wire/WireCmd.h b/generator/templates/dawn_wire/WireCmd.h
index 2d53008..a0052b7 100644
--- a/generator/templates/dawn_wire/WireCmd.h
+++ b/generator/templates/dawn_wire/WireCmd.h
@@ -128,6 +128,7 @@
         {% endfor %}
         BufferMapReadAsyncCallback,
         BufferMapWriteAsyncCallback,
+        FenceUpdateCompletedValue,
     };
 
     //* Command for the server calling a builder status callback.
diff --git a/generator/templates/dawn_wire/WireServer.cpp b/generator/templates/dawn_wire/WireServer.cpp
index ebc3417..9a81f9f 100644
--- a/generator/templates/dawn_wire/WireServer.cpp
+++ b/generator/templates/dawn_wire/WireServer.cpp
@@ -20,6 +20,7 @@
 #include <algorithm>
 #include <cstdlib>
 #include <cstring>
+#include <map>
 #include <vector>
 
 namespace dawn_wire {
@@ -36,6 +37,13 @@
             bool isWrite;
         };
 
+        struct FenceCompletionUserdata {
+            Server* server;
+            uint32_t fenceId;
+            uint32_t fenceSerial;
+            uint64_t value;
+        };
+
         //* Stores what the backend knows about the type.
         template<typename T>
         struct ObjectDataBase {
@@ -141,6 +149,36 @@
                 std::vector<Data> mKnown;
         };
 
+        // ObjectIds are lost in deserialization. Store the ids of deserialized
+        // objects here so they can be used in command handlers. This is useful
+        // for creating ReturnWireCmds which contain client ids
+        template <typename T>
+        class ObjectIdLookupTable {
+          public:
+            void Store(T key, ObjectId id) {
+                mTable[key] = id;
+            }
+
+            // Return the cached ObjectId, or 0 (null handle)
+            ObjectId Get(T key) const {
+                const auto it = mTable.find(key);
+                if (it != mTable.end()) {
+                    return it->second;
+                }
+                return 0;
+            }
+
+            void Remove(T key) {
+                auto it = mTable.find(key);
+                if (it != mTable.end()) {
+                    mTable.erase(it);
+                }
+            }
+
+          private:
+            std::map<T, ObjectId> mTable;
+        };
+
         void ForwardDeviceErrorToServer(const char* message, dawnCallbackUserdata userdata);
 
         {% for type in by_category["object"] if type.is_builder%}
@@ -149,6 +187,8 @@
 
         void ForwardBufferMapReadAsync(dawnBufferMapAsyncStatus status, const void* ptr, dawnCallbackUserdata userdata);
         void ForwardBufferMapWriteAsync(dawnBufferMapAsyncStatus status, void* ptr, dawnCallbackUserdata userdata);
+        void ForwardFenceCompletedValue(dawnFenceCompletionStatus status,
+                                        dawnCallbackUserdata userdata);
 
         // A really really simple implementation of the DeserializeAllocator. It's main feature
         // is that it has some inline storage so as to avoid allocations for the majority of
@@ -301,6 +341,19 @@
                     delete data;
                 }
 
+                void OnFenceCompletedValueUpdated(FenceCompletionUserdata* data) {
+                    ReturnFenceUpdateCompletedValueCmd cmd;
+                    cmd.fenceId = data->fenceId;
+                    cmd.fenceSerial = data->fenceSerial;
+                    cmd.value = data->value;
+
+                    auto allocCmd = static_cast<ReturnFenceUpdateCompletedValueCmd*>(GetCmdSpace(sizeof(cmd)));
+                    *allocCmd = cmd;
+
+                    delete data;
+                }
+
+                {% set client_side_commands = ["FenceGetCompletedValue"] %}
                 const char* HandleCommands(const char* commands, size_t size) override {
                     mProcs.deviceTick(mKnownDevice.Get(1)->handle);
 
@@ -312,9 +365,11 @@
                             {% for type in by_category["object"] %}
                                 {% for method in type.methods %}
                                     {% set Suffix = as_MethodSuffix(type.name, method.name) %}
-                                    case WireCmd::{{Suffix}}:
-                                        success = Handle{{Suffix}}(&commands, &size);
-                                        break;
+                                    {% if Suffix not in client_side_commands %}
+                                        case WireCmd::{{Suffix}}:
+                                            success = Handle{{Suffix}}(&commands, &size);
+                                            break;
+                                    {% endif %}
                                 {% endfor %}
                                 {% set Suffix = as_MethodSuffix(type.name, Name("destroy")) %}
                                 case WireCmd::{{Suffix}}:
@@ -386,6 +441,11 @@
                     KnownObjects<{{as_cType(type.name)}}> mKnown{{type.name.CamelCase()}};
                 {% endfor %}
 
+                {% set reverse_lookup_object_types = ["Fence"] %}
+                {% for type in by_category["object"] if type.name.CamelCase() in reverse_lookup_object_types %}
+                    ObjectIdLookupTable<{{as_cType(type.name)}}> m{{type.name.CamelCase()}}IdTable;
+                {% endfor %}
+
                 //* Helper function for the getting of the command data in command handlers.
                 //* Checks there is enough data left, updates the buffer / size and returns
                 //* the command (or nullptr for an error).
@@ -420,86 +480,119 @@
                     return true;
                 }
 
+                {% set custom_post_handler_commands = ["QueueSignal"] %}
+
+                bool PostHandleQueueSignal(const QueueSignalCmd& cmd) {
+                    ObjectId fenceId = mFenceIdTable.Get(cmd.fence);
+                    ASSERT(fenceId != 0);
+                    auto* fence = mKnownFence.Get(fenceId);
+                    ASSERT(fence != nullptr);
+
+                    auto* data = new FenceCompletionUserdata;
+                    data->server = this;
+                    data->fenceId = fenceId;
+                    data->fenceSerial = fence->serial;
+                    data->value = cmd.signalValue;
+
+                    auto userdata = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(data));
+                    mProcs.fenceOnCompletion(cmd.fence, cmd.signalValue, ForwardFenceCompletedValue, userdata);
+                    return true;
+                }
+
                 //* Implementation of the command handlers
                 {% for type in by_category["object"] %}
                     {% for method in type.methods %}
                         {% set Suffix = as_MethodSuffix(type.name, method.name) %}
+                        {% if Suffix not in client_side_commands %}
+                            //* The generic command handlers
 
-                        //* The generic command handlers
+                            bool Handle{{Suffix}}(const char** commands, size_t* size) {
+                                {{Suffix}}Cmd cmd;
+                                DeserializeResult deserializeResult = cmd.Deserialize(commands, size, &mAllocator, *this);
 
-                        bool Handle{{Suffix}}(const char** commands, size_t* size) {
-                            {{Suffix}}Cmd cmd;
-                            DeserializeResult deserializeResult = cmd.Deserialize(commands, size, &mAllocator, *this);
-
-                            if (deserializeResult == DeserializeResult::FatalError) {
-                                return false;
-                            }
-
-                            {% if Suffix in custom_pre_handler_commands %}
-                                if (!PreHandle{{Suffix}}(cmd)) {
+                                if (deserializeResult == DeserializeResult::FatalError) {
                                     return false;
                                 }
-                            {% endif %}
 
-                            //* Unpack 'self'
-                            auto* selfData = mKnown{{type.name.CamelCase()}}.Get(cmd.selfId);
-                            ASSERT(selfData != nullptr);
-
-                            //* In all cases allocate the object data as it will be refered-to by the client.
-                            {% set return_type = method.return_type %}
-                            {% set returns = return_type.name.canonical_case() != "void" %}
-                            {% if returns %}
-                                {% set Type = method.return_type.name.CamelCase() %}
-                                auto* resultData = mKnown{{Type}}.Allocate(cmd.resultId);
-                                if (resultData == nullptr) {
-                                    return false;
-                                }
-                                resultData->serial = cmd.resultSerial;
-
-                                {% if type.is_builder %}
-                                    selfData->builtObjectId = cmd.resultId;
-                                    selfData->builtObjectSerial = cmd.resultSerial;
-                                {% endif %}
-                            {% endif %}
-
-                            //* After the data is allocated, apply the argument error propagation mechanism
-                            if (deserializeResult == DeserializeResult::ErrorObject) {
-                                {% if type.is_builder %}
-                                    selfData->valid = false;
-                                    //* If we are in GetResult, fake an error callback
-                                    {% if returns %}
-                                        On{{type.name.CamelCase()}}Error(DAWN_BUILDER_ERROR_STATUS_ERROR, "Maybe monad", cmd.selfId, selfData->serial);
-                                    {% endif %}
-                                {% endif %}
-                                return true;
-                            }
-
-                            {% if returns %}
-                                auto result ={{" "}}
-                            {%- endif %}
-                            mProcs.{{as_varName(type.name, method.name)}}(cmd.self
-                                {%- for arg in method.arguments -%}
-                                    , cmd.{{as_varName(arg.name)}}
-                                {%- endfor -%}
-                            );
-
-                            {% if returns %}
-                                resultData->handle = result;
-                                resultData->valid = result != nullptr;
-
-                                //* builders remember the ID of the object they built so that they can send it
-                                //* in the callback to the client.
-                                {% if return_type.is_builder %}
-                                    if (result != nullptr) {
-                                        uint64_t userdata1 = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(this));
-                                        uint64_t userdata2 = (uint64_t(resultData->serial) << uint64_t(32)) + cmd.resultId;
-                                        mProcs.{{as_varName(return_type.name, Name("set error callback"))}}(result, Forward{{return_type.name.CamelCase()}}ToClient, userdata1, userdata2);
+                                {% if Suffix in custom_pre_handler_commands %}
+                                    if (!PreHandle{{Suffix}}(cmd)) {
+                                        return false;
                                     }
                                 {% endif %}
-                            {% endif %}
 
-                            return true;
-                        }
+                                //* Unpack 'self'
+                                auto* selfData = mKnown{{type.name.CamelCase()}}.Get(cmd.selfId);
+                                ASSERT(selfData != nullptr);
+
+                                //* In all cases allocate the object data as it will be refered-to by the client.
+                                {% set return_type = method.return_type %}
+                                {% set returns = return_type.name.canonical_case() != "void" %}
+                                {% if returns %}
+                                    {% set Type = method.return_type.name.CamelCase() %}
+                                    auto* resultData = mKnown{{Type}}.Allocate(cmd.resultId);
+                                    if (resultData == nullptr) {
+                                        return false;
+                                    }
+                                    resultData->serial = cmd.resultSerial;
+
+                                    {% if type.is_builder %}
+                                        selfData->builtObjectId = cmd.resultId;
+                                        selfData->builtObjectSerial = cmd.resultSerial;
+                                    {% endif %}
+                                {% endif %}
+
+                                //* After the data is allocated, apply the argument error propagation mechanism
+                                if (deserializeResult == DeserializeResult::ErrorObject) {
+                                    {% if type.is_builder %}
+                                        selfData->valid = false;
+                                        //* If we are in GetResult, fake an error callback
+                                        {% if returns %}
+                                            On{{type.name.CamelCase()}}Error(DAWN_BUILDER_ERROR_STATUS_ERROR, "Maybe monad", cmd.selfId, selfData->serial);
+                                        {% endif %}
+                                    {% endif %}
+                                    return true;
+                                }
+
+                                {% if returns %}
+                                    auto result ={{" "}}
+                                {%- endif %}
+                                mProcs.{{as_varName(type.name, method.name)}}(cmd.self
+                                    {%- for arg in method.arguments -%}
+                                        , cmd.{{as_varName(arg.name)}}
+                                    {%- endfor -%}
+                                );
+
+                                {% if Suffix in custom_post_handler_commands %}
+                                    if (!PostHandle{{Suffix}}(cmd)) {
+                                        return false;
+                                    }
+                                {% endif %}
+
+                                {% if returns %}
+                                    resultData->handle = result;
+                                    resultData->valid = result != nullptr;
+
+                                    {% if return_type.name.CamelCase() in reverse_lookup_object_types %}
+                                        //* For created objects, store a mapping from them back to their client IDs
+                                        if (result) {
+                                            m{{return_type.name.CamelCase()}}IdTable.Store(result, cmd.resultId);
+                                        }
+                                    {% endif %}
+
+                                    //* builders remember the ID of the object they built so that they can send it
+                                    //* in the callback to the client.
+                                    {% if return_type.is_builder %}
+                                        if (result != nullptr) {
+                                            uint64_t userdata1 = static_cast<uint64_t>(reinterpret_cast<uintptr_t>(this));
+                                            uint64_t userdata2 = (uint64_t(resultData->serial) << uint64_t(32)) + cmd.resultId;
+                                            mProcs.{{as_varName(return_type.name, Name("set error callback"))}}(result, Forward{{return_type.name.CamelCase()}}ToClient, userdata1, userdata2);
+                                        }
+                                    {% endif %}
+                                {% endif %}
+
+                                return true;
+                            }
+                        {% endif %}
                     {% endfor %}
 
                     //* Handlers for the destruction of objects: clients do the tracking of the
@@ -523,6 +616,10 @@
                             return false;
                         }
 
+                        {% if type.name.CamelCase() in reverse_lookup_object_types %}
+                            m{{type.name.CamelCase()}}IdTable.Remove(data->handle);
+                        {% endif %}
+
                         if (data->valid) {
                             mProcs.{{as_varName(type.name, Name("release"))}}(data->handle);
                         }
@@ -639,6 +736,13 @@
             auto data = reinterpret_cast<MapUserdata*>(static_cast<uintptr_t>(userdata));
             data->server->OnMapWriteAsyncCallback(status, ptr, data);
         }
+
+        void ForwardFenceCompletedValue(dawnFenceCompletionStatus status, dawnCallbackUserdata userdata) {
+            auto data = reinterpret_cast<FenceCompletionUserdata*>(static_cast<uintptr_t>(userdata));
+            if (status == DAWN_FENCE_COMPLETION_STATUS_SUCCESS) {
+                data->server->OnFenceCompletedValueUpdated(data);
+            }
+        }
     }
 
     CommandHandler* NewServerCommandHandler(dawnDevice device, const dawnProcTable& procs, CommandSerializer* serializer) {
diff --git a/generator/templates/mock_api.cpp b/generator/templates/mock_api.cpp
index 3c39d71..447bd9f 100644
--- a/generator/templates/mock_api.cpp
+++ b/generator/templates/mock_api.cpp
@@ -72,6 +72,17 @@
     OnBufferMapWriteAsyncCallback(self, start, size, callback, userdata);
 }
 
+void ProcTableAsClass::FenceOnCompletion(dawnFence self,
+                                         uint64_t value,
+                                         dawnFenceOnCompletionCallback callback,
+                                         dawnCallbackUserdata userdata) {
+    auto object = reinterpret_cast<ProcTableAsClass::Object*>(self);
+    object->fenceOnCompletionCallback = callback;
+    object->userdata1 = userdata;
+
+    OnFenceOnCompletionCallback(self, value, callback, userdata);
+}
+
 void ProcTableAsClass::CallDeviceErrorCallback(dawnDevice device, const char* message) {
     auto object = reinterpret_cast<ProcTableAsClass::Object*>(device);
     object->deviceErrorCallback(message, object->userdata1);
@@ -90,6 +101,12 @@
     object->mapWriteCallback(status, data, object->userdata1);
 }
 
+void ProcTableAsClass::CallFenceOnCompletionCallback(dawnFence fence,
+                                                     dawnFenceCompletionStatus status) {
+    auto object = reinterpret_cast<ProcTableAsClass::Object*>(fence);
+    object->fenceOnCompletionCallback(status, object->userdata1);
+}
+
 {% for type in by_category["object"] if type.is_builder %}
     void ProcTableAsClass::{{as_MethodSuffix(type.name, Name("set error callback"))}}({{as_cType(type.name)}} self, dawnBuilderErrorCallback callback, dawnCallbackUserdata userdata1, dawnCallbackUserdata userdata2) {
         auto object = reinterpret_cast<ProcTableAsClass::Object*>(self);
diff --git a/generator/templates/mock_api.h b/generator/templates/mock_api.h
index b82a22a..da3c60e 100644
--- a/generator/templates/mock_api.h
+++ b/generator/templates/mock_api.h
@@ -59,19 +59,27 @@
         void DeviceSetErrorCallback(dawnDevice self, dawnDeviceErrorCallback callback, dawnCallbackUserdata userdata);
         void BufferMapReadAsync(dawnBuffer self, uint32_t start, uint32_t size, dawnBufferMapReadCallback callback, dawnCallbackUserdata userdata);
         void BufferMapWriteAsync(dawnBuffer self, uint32_t start, uint32_t size, dawnBufferMapWriteCallback callback, dawnCallbackUserdata userdata);
-
+        void FenceOnCompletion(dawnFence self,
+                               uint64_t value,
+                               dawnFenceOnCompletionCallback callback,
+                               dawnCallbackUserdata userdata);
 
         // Special cased mockable methods
         virtual void OnDeviceSetErrorCallback(dawnDevice device, dawnDeviceErrorCallback callback, dawnCallbackUserdata userdata) = 0;
         virtual void OnBuilderSetErrorCallback(dawnBufferBuilder builder, dawnBuilderErrorCallback callback, dawnCallbackUserdata userdata1, dawnCallbackUserdata userdata2) = 0;
         virtual void OnBufferMapReadAsyncCallback(dawnBuffer buffer, uint32_t start, uint32_t size, dawnBufferMapReadCallback callback, dawnCallbackUserdata userdata) = 0;
         virtual void OnBufferMapWriteAsyncCallback(dawnBuffer buffer, uint32_t start, uint32_t size, dawnBufferMapWriteCallback callback, dawnCallbackUserdata userdata) = 0;
+        virtual void OnFenceOnCompletionCallback(dawnFence fence,
+                                                 uint64_t value,
+                                                 dawnFenceOnCompletionCallback callback,
+                                                 dawnCallbackUserdata userdata) = 0;
 
         // Calls the stored callbacks
         void CallDeviceErrorCallback(dawnDevice device, const char* message);
         void CallBuilderErrorCallback(void* builder , dawnBuilderErrorStatus status, const char* message);
         void CallMapReadCallback(dawnBuffer buffer, dawnBufferMapAsyncStatus status, const void* data);
         void CallMapWriteCallback(dawnBuffer buffer, dawnBufferMapAsyncStatus status, void* data);
+        void CallFenceOnCompletionCallback(dawnFence fence, dawnFenceCompletionStatus status);
 
         struct Object {
             ProcTableAsClass* procs = nullptr;
@@ -79,6 +87,7 @@
             dawnBuilderErrorCallback builderErrorCallback = nullptr;
             dawnBufferMapReadCallback mapReadCallback = nullptr;
             dawnBufferMapWriteCallback mapWriteCallback = nullptr;
+            dawnFenceOnCompletionCallback fenceOnCompletionCallback = nullptr;
             dawnCallbackUserdata userdata1 = 0;
             dawnCallbackUserdata userdata2 = 0;
         };
@@ -112,6 +121,11 @@
         MOCK_METHOD4(OnBuilderSetErrorCallback, void(dawnBufferBuilder builder, dawnBuilderErrorCallback callback, dawnCallbackUserdata userdata1, dawnCallbackUserdata userdata2));
         MOCK_METHOD5(OnBufferMapReadAsyncCallback, void(dawnBuffer buffer, uint32_t start, uint32_t size, dawnBufferMapReadCallback callback, dawnCallbackUserdata userdata));
         MOCK_METHOD5(OnBufferMapWriteAsyncCallback, void(dawnBuffer buffer, uint32_t start, uint32_t size, dawnBufferMapWriteCallback callback, dawnCallbackUserdata userdata));
+        MOCK_METHOD4(OnFenceOnCompletionCallback,
+                     void(dawnFence fence,
+                          uint64_t value,
+                          dawnFenceOnCompletionCallback callback,
+                          dawnCallbackUserdata userdata));
 };
 
 #endif // MOCK_DAWN_H
diff --git a/src/dawn_native/Device.cpp b/src/dawn_native/Device.cpp
index f2581cd..0ab1323 100644
--- a/src/dawn_native/Device.cpp
+++ b/src/dawn_native/Device.cpp
@@ -22,6 +22,8 @@
 #include "dawn_native/ComputePipeline.h"
 #include "dawn_native/DepthStencilState.h"
 #include "dawn_native/ErrorData.h"
+#include "dawn_native/Fence.h"
+#include "dawn_native/FenceSignalTracker.h"
 #include "dawn_native/InputState.h"
 #include "dawn_native/PipelineLayout.h"
 #include "dawn_native/Queue.h"
@@ -51,6 +53,7 @@
 
     DeviceBase::DeviceBase() {
         mCaches = std::make_unique<DeviceBase::Caches>();
+        mFenceSignalTracker = std::make_unique<FenceSignalTracker>(this);
     }
 
     DeviceBase::~DeviceBase() {
@@ -72,6 +75,10 @@
         return this;
     }
 
+    FenceSignalTracker* DeviceBase::GetFenceSignalTracker() const {
+        return mFenceSignalTracker.get();
+    }
+
     ResultOrError<BindGroupLayoutBase*> DeviceBase::GetOrCreateBindGroupLayout(
         const BindGroupLayoutDescriptor* descriptor) {
         BindGroupLayoutBase blueprint(this, descriptor, true);
@@ -135,6 +142,15 @@
     DepthStencilStateBuilder* DeviceBase::CreateDepthStencilStateBuilder() {
         return new DepthStencilStateBuilder(this);
     }
+    FenceBase* DeviceBase::CreateFence(const FenceDescriptor* descriptor) {
+        FenceBase* result = nullptr;
+
+        if (ConsumedError(CreateFenceInternal(&result, descriptor))) {
+            return nullptr;
+        }
+
+        return result;
+    }
     InputStateBuilder* DeviceBase::CreateInputStateBuilder() {
         return new InputStateBuilder(this);
     }
@@ -206,6 +222,7 @@
 
     void DeviceBase::Tick() {
         TickImpl();
+        mFenceSignalTracker->Tick(GetCompletedCommandSerial());
     }
 
     void DeviceBase::Reference() {
@@ -246,6 +263,13 @@
         return {};
     }
 
+    MaybeError DeviceBase::CreateFenceInternal(FenceBase** result,
+                                               const FenceDescriptor* descriptor) {
+        DAWN_TRY(ValidateFenceDescriptor(this, descriptor));
+        *result = new FenceBase(this, descriptor);
+        return {};
+    }
+
     MaybeError DeviceBase::CreatePipelineLayoutInternal(
         PipelineLayoutBase** result,
         const PipelineLayoutDescriptor* descriptor) {
diff --git a/src/dawn_native/Device.h b/src/dawn_native/Device.h
index 16b15d4..cbb5af6 100644
--- a/src/dawn_native/Device.h
+++ b/src/dawn_native/Device.h
@@ -29,6 +29,8 @@
 
     using ErrorCallback = void (*)(const char* errorMessage, void* userData);
 
+    class FenceSignalTracker;
+
     class DeviceBase {
       public:
         DeviceBase();
@@ -47,6 +49,8 @@
         // Used by autogenerated code, returns itself
         DeviceBase* GetDevice();
 
+        FenceSignalTracker* GetFenceSignalTracker() const;
+
         virtual BindGroupBase* CreateBindGroup(BindGroupBuilder* builder) = 0;
         virtual BlendStateBase* CreateBlendState(BlendStateBuilder* builder) = 0;
         virtual BufferViewBase* CreateBufferView(BufferViewBuilder* builder) = 0;
@@ -89,6 +93,7 @@
         CommandBufferBuilder* CreateCommandBufferBuilder();
         ComputePipelineBase* CreateComputePipeline(const ComputePipelineDescriptor* descriptor);
         DepthStencilStateBuilder* CreateDepthStencilStateBuilder();
+        FenceBase* CreateFence(const FenceDescriptor* descriptor);
         InputStateBuilder* CreateInputStateBuilder();
         PipelineLayoutBase* CreatePipelineLayout(const PipelineLayoutDescriptor* descriptor);
         QueueBase* CreateQueue();
@@ -137,6 +142,7 @@
         MaybeError CreateBufferInternal(BufferBase** result, const BufferDescriptor* descriptor);
         MaybeError CreateComputePipelineInternal(ComputePipelineBase** result,
                                                  const ComputePipelineDescriptor* descriptor);
+        MaybeError CreateFenceInternal(FenceBase** result, const FenceDescriptor* descriptor);
         MaybeError CreatePipelineLayoutInternal(PipelineLayoutBase** result,
                                                 const PipelineLayoutDescriptor* descriptor);
         MaybeError CreateQueueInternal(QueueBase** result);
@@ -155,6 +161,8 @@
         struct Caches;
         std::unique_ptr<Caches> mCaches;
 
+        std::unique_ptr<FenceSignalTracker> mFenceSignalTracker;
+
         dawn::DeviceErrorCallback mErrorCallback = nullptr;
         dawn::CallbackUserdata mErrorUserdata = 0;
         uint32_t mRefCount = 1;
diff --git a/src/dawn_native/Fence.cpp b/src/dawn_native/Fence.cpp
new file mode 100644
index 0000000..7906c38
--- /dev/null
+++ b/src/dawn_native/Fence.cpp
@@ -0,0 +1,99 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "dawn_native/Fence.h"
+
+#include "common/Assert.h"
+#include "dawn_native/Device.h"
+#include "dawn_native/ValidationUtils_autogen.h"
+
+#include <cstdio>
+#include <utility>
+
+namespace dawn_native {
+
+    MaybeError ValidateFenceDescriptor(DeviceBase*, const FenceDescriptor* descriptor) {
+        if (descriptor->nextInChain != nullptr) {
+            return DAWN_VALIDATION_ERROR("nextInChain must be nullptr");
+        }
+
+        return {};
+    }
+
+    // Fence
+
+    FenceBase::FenceBase(DeviceBase* device, const FenceDescriptor* descriptor)
+        : ObjectBase(device),
+          mSignalValue(descriptor->initialValue),
+          mCompletedValue(descriptor->initialValue) {
+    }
+
+    FenceBase::~FenceBase() {
+        for (auto& request : mRequests.IterateAll()) {
+            request.completionCallback(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, request.userdata);
+        }
+        mRequests.Clear();
+    }
+
+    uint64_t FenceBase::GetCompletedValue() const {
+        return mCompletedValue;
+    }
+
+    void FenceBase::OnCompletion(uint64_t value,
+                                 dawn::FenceOnCompletionCallback callback,
+                                 dawn::CallbackUserdata userdata) {
+        if (GetDevice()->ConsumedError(ValidateOnCompletion(value))) {
+            callback(DAWN_FENCE_COMPLETION_STATUS_ERROR, userdata);
+            return;
+        }
+
+        if (value <= mCompletedValue) {
+            callback(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata);
+            return;
+        }
+
+        OnCompletionData request;
+        request.completionCallback = callback;
+        request.userdata = userdata;
+        mRequests.Enqueue(std::move(request), value);
+    }
+
+    uint64_t FenceBase::GetSignaledValue() const {
+        return mSignalValue;
+    }
+
+    void FenceBase::SetSignaledValue(uint64_t signalValue) {
+        ASSERT(signalValue > mSignalValue);
+        mSignalValue = signalValue;
+    }
+
+    void FenceBase::SetCompletedValue(uint64_t completedValue) {
+        ASSERT(completedValue <= mSignalValue);
+        ASSERT(completedValue > mCompletedValue);
+        mCompletedValue = completedValue;
+
+        for (auto& request : mRequests.IterateUpTo(mCompletedValue)) {
+            request.completionCallback(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, request.userdata);
+        }
+        mRequests.ClearUpTo(mCompletedValue);
+    }
+
+    MaybeError FenceBase::ValidateOnCompletion(uint64_t value) const {
+        if (value > mSignalValue) {
+            return DAWN_VALIDATION_ERROR("Value greater than fence signaled value");
+        }
+        return {};
+    }
+
+}  // namespace dawn_native
diff --git a/src/dawn_native/Fence.h b/src/dawn_native/Fence.h
new file mode 100644
index 0000000..e2f4c40
--- /dev/null
+++ b/src/dawn_native/Fence.h
@@ -0,0 +1,64 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef DAWNNATIVE_FENCE_H_
+#define DAWNNATIVE_FENCE_H_
+
+#include "common/SerialMap.h"
+#include "dawn_native/Error.h"
+#include "dawn_native/Forward.h"
+#include "dawn_native/ObjectBase.h"
+
+#include "dawn_native/dawn_platform.h"
+
+#include <map>
+
+namespace dawn_native {
+
+    MaybeError ValidateFenceDescriptor(DeviceBase*, const FenceDescriptor* descriptor);
+
+    class FenceBase : public ObjectBase {
+      public:
+        FenceBase(DeviceBase* device, const FenceDescriptor* descriptor);
+        ~FenceBase();
+
+        // Dawn API
+        uint64_t GetCompletedValue() const;
+        void OnCompletion(uint64_t value,
+                          dawn::FenceOnCompletionCallback callback,
+                          dawn::CallbackUserdata userdata);
+        uint64_t GetSignaledValue() const;
+
+      protected:
+        friend class QueueBase;
+        friend class FenceSignalTracker;
+        void SetSignaledValue(uint64_t signalValue);
+        void SetCompletedValue(uint64_t completedValue);
+
+      private:
+        MaybeError ValidateOnCompletion(uint64_t value) const;
+
+        struct OnCompletionData {
+            dawn::FenceOnCompletionCallback completionCallback = nullptr;
+            dawn::CallbackUserdata userdata = 0;
+        };
+
+        uint64_t mSignalValue;
+        uint64_t mCompletedValue;
+        SerialMap<OnCompletionData> mRequests;
+    };
+
+}  // namespace dawn_native
+
+#endif  // DAWNNATIVE_FENCE_H_
diff --git a/src/dawn_native/FenceSignalTracker.cpp b/src/dawn_native/FenceSignalTracker.cpp
new file mode 100644
index 0000000..132ac9c
--- /dev/null
+++ b/src/dawn_native/FenceSignalTracker.cpp
@@ -0,0 +1,43 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "dawn_native/FenceSignalTracker.h"
+
+#include "dawn_native/Device.h"
+#include "dawn_native/Fence.h"
+
+namespace dawn_native {
+
+    FenceSignalTracker::FenceSignalTracker(DeviceBase* device) : mDevice(device) {
+    }
+
+    FenceSignalTracker::~FenceSignalTracker() {
+        ASSERT(mFencesInFlight.Empty());
+    }
+
+    void FenceSignalTracker::UpdateFenceOnComplete(FenceBase* fence, uint64_t value) {
+        // Because we currently only have a single queue, we can simply update
+        // the fence completed value once the last submitted serial has passed.
+        mFencesInFlight.Enqueue(FenceInFlight{fence, value},
+                                mDevice->GetLastSubmittedCommandSerial());
+    }
+
+    void FenceSignalTracker::Tick(Serial finishedSerial) {
+        for (auto& fenceInFlight : mFencesInFlight.IterateUpTo(finishedSerial)) {
+            fenceInFlight.fence->SetCompletedValue(fenceInFlight.value);
+        }
+        mFencesInFlight.ClearUpTo(finishedSerial);
+    }
+
+}  // namespace dawn_native
diff --git a/src/dawn_native/FenceSignalTracker.h b/src/dawn_native/FenceSignalTracker.h
new file mode 100644
index 0000000..d689277
--- /dev/null
+++ b/src/dawn_native/FenceSignalTracker.h
@@ -0,0 +1,47 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef DAWNNATIVE_FENCESIGNALTRACKER_H_
+#define DAWNNATIVE_FENCESIGNALTRACKER_H_
+
+#include "common/SerialQueue.h"
+#include "dawn_native/RefCounted.h"
+
+namespace dawn_native {
+
+    class DeviceBase;
+    class FenceBase;
+
+    class FenceSignalTracker {
+        struct FenceInFlight {
+            Ref<FenceBase> fence;
+            uint64_t value;
+        };
+
+      public:
+        FenceSignalTracker(DeviceBase* device);
+        ~FenceSignalTracker();
+
+        void UpdateFenceOnComplete(FenceBase* fence, uint64_t value);
+
+        void Tick(Serial finishedSerial);
+
+      private:
+        DeviceBase* mDevice;
+        SerialQueue<FenceInFlight> mFencesInFlight;
+    };
+
+}  // namespace dawn_native
+
+#endif  // DAWNNATIVE_FENCESIGNALTRACKER_H_
diff --git a/src/dawn_native/Forward.h b/src/dawn_native/Forward.h
index a5ac6e4..1705d72 100644
--- a/src/dawn_native/Forward.h
+++ b/src/dawn_native/Forward.h
@@ -36,6 +36,7 @@
     class ComputePassEncoderBase;
     class DepthStencilStateBase;
     class DepthStencilStateBuilder;
+    class FenceBase;
     class InputStateBase;
     class InputStateBuilder;
     class PipelineLayoutBase;
diff --git a/src/dawn_native/Queue.cpp b/src/dawn_native/Queue.cpp
index 021a095..6ed84ad 100644
--- a/src/dawn_native/Queue.cpp
+++ b/src/dawn_native/Queue.cpp
@@ -17,6 +17,8 @@
 #include "dawn_native/Buffer.h"
 #include "dawn_native/CommandBuffer.h"
 #include "dawn_native/Device.h"
+#include "dawn_native/Fence.h"
+#include "dawn_native/FenceSignalTracker.h"
 #include "dawn_native/Texture.h"
 
 namespace dawn_native {
@@ -34,6 +36,15 @@
         SubmitImpl(numCommands, commands);
     }
 
+    void QueueBase::Signal(FenceBase* fence, uint64_t signalValue) {
+        if (GetDevice()->ConsumedError(ValidateSignal(fence, signalValue))) {
+            return;
+        }
+
+        fence->SetSignaledValue(signalValue);
+        GetDevice()->GetFenceSignalTracker()->UpdateFenceOnComplete(fence, signalValue);
+    }
+
     MaybeError QueueBase::ValidateSubmit(uint32_t numCommands, CommandBufferBase* const* commands) {
         for (uint32_t i = 0; i < numCommands; ++i) {
             const CommandBufferResourceUsage& usages = commands[i]->GetResourceUsages();
@@ -58,4 +69,11 @@
         return {};
     }
 
+    MaybeError QueueBase::ValidateSignal(const FenceBase* fence, uint64_t signalValue) {
+        if (signalValue <= fence->GetSignaledValue()) {
+            return DAWN_VALIDATION_ERROR("Signal value less than or equal to fence signaled value");
+        }
+        return {};
+    }
+
 }  // namespace dawn_native
diff --git a/src/dawn_native/Queue.h b/src/dawn_native/Queue.h
index a9655f2..0a85af4 100644
--- a/src/dawn_native/Queue.h
+++ b/src/dawn_native/Queue.h
@@ -30,11 +30,13 @@
 
         // Dawn API
         void Submit(uint32_t numCommands, CommandBufferBase* const* commands);
+        void Signal(FenceBase* fence, uint64_t signalValue);
 
       private:
         virtual void SubmitImpl(uint32_t numCommands, CommandBufferBase* const* commands) = 0;
 
         MaybeError ValidateSubmit(uint32_t numCommands, CommandBufferBase* const* commands);
+        MaybeError ValidateSignal(const FenceBase* fence, uint64_t signalValue);
     };
 
 }  // namespace dawn_native
diff --git a/src/dawn_wire/WireCmd.h b/src/dawn_wire/WireCmd.h
index 7419cd2..5d6c371 100644
--- a/src/dawn_wire/WireCmd.h
+++ b/src/dawn_wire/WireCmd.h
@@ -56,6 +56,14 @@
         uint32_t status;
     };
 
+    struct ReturnFenceUpdateCompletedValueCmd {
+        ReturnWireCmd commandId = ReturnWireCmd::FenceUpdateCompletedValue;
+
+        ObjectId fenceId;
+        ObjectSerial fenceSerial;
+        uint64_t value;
+    };
+
     struct BufferUpdateMappedDataCmd {
         WireCmd commandId = WireCmd::BufferUpdateMappedDataCmd;
 
diff --git a/src/tests/end2end/FenceTests.cpp b/src/tests/end2end/FenceTests.cpp
new file mode 100644
index 0000000..8fdba65
--- /dev/null
+++ b/src/tests/end2end/FenceTests.cpp
@@ -0,0 +1,227 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <gmock/gmock.h>
+#include "tests/DawnTest.h"
+
+#include <array>
+#include <cstring>
+
+class MockFenceOnCompletionCallback {
+  public:
+    MOCK_METHOD2(Call, void(dawnFenceCompletionStatus status, dawnCallbackUserdata userdata));
+};
+
+static std::unique_ptr<MockFenceOnCompletionCallback> mockFenceOnCompletionCallback;
+static void ToMockFenceOnCompletionCallback(dawnFenceCompletionStatus status,
+                                            dawnCallbackUserdata userdata) {
+    mockFenceOnCompletionCallback->Call(status, userdata);
+}
+class FenceTests : public DawnTest {
+  private:
+    struct CallbackInfo {
+        FenceTests* test;
+        uint64_t value;
+        dawnFenceCompletionStatus status;
+        int32_t callIndex = -1;  // If this is -1, the callback was not called
+
+        void Update(dawnFenceCompletionStatus status) {
+            this->callIndex = test->mCallIndex++;
+            this->status = status;
+        }
+    };
+
+    int32_t mCallIndex;
+
+  protected:
+    FenceTests() : mCallIndex(0) {
+    }
+
+    void SetUp() override {
+        DawnTest::SetUp();
+        mockFenceOnCompletionCallback = std::make_unique<MockFenceOnCompletionCallback>();
+    }
+
+    void TearDown() override {
+        mockFenceOnCompletionCallback = nullptr;
+        DawnTest::TearDown();
+    }
+
+    void WaitForCompletedValue(dawn::Fence fence, uint64_t completedValue) {
+        while (fence.GetCompletedValue() < completedValue) {
+            WaitABit();
+        }
+    }
+};
+
+// Test that signaling a fence updates the completed value
+TEST_P(FenceTests, SimpleSignal) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1u;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    // Completed value starts at initial value
+    EXPECT_EQ(fence.GetCompletedValue(), 1u);
+
+    queue.Signal(fence, 2);
+    WaitForCompletedValue(fence, 2);
+
+    // Completed value updates to signaled value
+    EXPECT_EQ(fence.GetCompletedValue(), 2u);
+}
+
+// Test callbacks are called in increasing order of fence completion value
+TEST_P(FenceTests, OnCompletionOrdering) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 0u;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    queue.Signal(fence, 4);
+
+    dawnCallbackUserdata userdata0 = 1282;
+    dawnCallbackUserdata userdata1 = 4382;
+    dawnCallbackUserdata userdata2 = 1211;
+    dawnCallbackUserdata userdata3 = 1882;
+
+    {
+        testing::InSequence s;
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata0))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata1))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata2))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata3))
+            .Times(1);
+    }
+
+    fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, userdata2);
+    fence.OnCompletion(0u, ToMockFenceOnCompletionCallback, userdata0);
+    fence.OnCompletion(3u, ToMockFenceOnCompletionCallback, userdata3);
+    fence.OnCompletion(1u, ToMockFenceOnCompletionCallback, userdata1);
+
+    WaitForCompletedValue(fence, 4);
+}
+
+// Test callbacks still occur if Queue::Signal happens multiple times
+TEST_P(FenceTests, MultipleSignalOnCompletion) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 0u;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    queue.Signal(fence, 2);
+    queue.Signal(fence, 4);
+
+    dawnCallbackUserdata userdata = 1234;
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata))
+        .Times(1);
+    fence.OnCompletion(3u, ToMockFenceOnCompletionCallback, userdata);
+
+    WaitForCompletedValue(fence, 4);
+}
+
+// Test all callbacks are called if they are added for the same fence value
+TEST_P(FenceTests, OnCompletionMultipleCallbacks) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 0u;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    queue.Signal(fence, 4);
+
+    dawnCallbackUserdata userdata0 = 2341;
+    dawnCallbackUserdata userdata1 = 4598;
+    dawnCallbackUserdata userdata2 = 5690;
+    dawnCallbackUserdata userdata3 = 2783;
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata0))
+        .Times(1);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata1))
+        .Times(1);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata2))
+        .Times(1);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata3))
+        .Times(1);
+
+    fence.OnCompletion(4u, ToMockFenceOnCompletionCallback, userdata0);
+    fence.OnCompletion(4u, ToMockFenceOnCompletionCallback, userdata1);
+    fence.OnCompletion(4u, ToMockFenceOnCompletionCallback, userdata2);
+    fence.OnCompletion(4u, ToMockFenceOnCompletionCallback, userdata3);
+
+    WaitForCompletedValue(fence, 4u);
+}
+
+// TODO(enga): Enable when fence is removed from fence signal tracker
+// Currently it holds a reference and is not destructed
+TEST_P(FenceTests, DISABLED_DestroyBeforeOnCompletionEnd) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 0u;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    // The fence in this block will be deleted when it goes out of scope
+    {
+        dawn::FenceDescriptor descriptor;
+        descriptor.initialValue = 0u;
+        dawn::Fence testFence = device.CreateFence(&descriptor);
+
+        queue.Signal(testFence, 4);
+
+        dawnCallbackUserdata userdata0 = 1341;
+        dawnCallbackUserdata userdata1 = 1598;
+        dawnCallbackUserdata userdata2 = 1690;
+        dawnCallbackUserdata userdata3 = 1783;
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, userdata0))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, userdata1))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, userdata2))
+            .Times(1);
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, userdata3))
+            .Times(1);
+
+        testFence.OnCompletion(1u, ToMockFenceOnCompletionCallback, userdata0);
+        testFence.OnCompletion(2u, ToMockFenceOnCompletionCallback, userdata1);
+        testFence.OnCompletion(2u, ToMockFenceOnCompletionCallback, userdata2);
+        testFence.OnCompletion(3u, ToMockFenceOnCompletionCallback, userdata3);
+    }
+
+    // Wait for another fence to be sure all callbacks have cleared
+    queue.Signal(fence, 1);
+    WaitForCompletedValue(fence, 1);
+}
+
+DAWN_INSTANTIATE_TEST(FenceTests, D3D12Backend, MetalBackend, OpenGLBackend, VulkanBackend)
diff --git a/src/tests/unittests/WireTests.cpp b/src/tests/unittests/WireTests.cpp
index 17ab909..b8f3002 100644
--- a/src/tests/unittests/WireTests.cpp
+++ b/src/tests/unittests/WireTests.cpp
@@ -117,6 +117,17 @@
     mockBufferMapWriteCallback->Call(status, lastMapWritePointer, userdata);
 }
 
+class MockFenceOnCompletionCallback {
+  public:
+    MOCK_METHOD2(Call, void(dawnFenceCompletionStatus status, dawnCallbackUserdata userdata));
+};
+
+static std::unique_ptr<MockFenceOnCompletionCallback> mockFenceOnCompletionCallback;
+static void ToMockFenceOnCompletionCallback(dawnFenceCompletionStatus status,
+                                            dawnCallbackUserdata userdata) {
+    mockFenceOnCompletionCallback->Call(status, userdata);
+}
+
 class WireTestsBase : public Test {
     protected:
         WireTestsBase(bool ignoreSetCallbackCalls)
@@ -128,6 +139,7 @@
             mockBuilderErrorCallback = std::make_unique<MockBuilderErrorCallback>();
             mockBufferMapReadCallback = std::make_unique<MockBufferMapReadCallback>();
             mockBufferMapWriteCallback = std::make_unique<MockBufferMapWriteCallback>();
+            mockFenceOnCompletionCallback = std::make_unique<MockFenceOnCompletionCallback>();
 
             dawnProcTable mockProcs;
             dawnDevice mockDevice;
@@ -162,6 +174,7 @@
             mockBuilderErrorCallback = nullptr;
             mockBufferMapReadCallback = nullptr;
             mockBufferMapWriteCallback = nullptr;
+            mockFenceOnCompletionCallback = nullptr;
         }
 
         void FlushClient() {
@@ -791,7 +804,7 @@
 TEST_F(WireBufferMappingTests, MappingForReadSuccessBuffer) {
     dawnCallbackUserdata userdata = 8653;
     dawnBufferMapReadAsync(buffer, 40, sizeof(uint32_t), ToMockBufferMapReadCallback, userdata);
-    
+
     uint32_t bufferContent = 31337;
     EXPECT_CALL(api, OnBufferMapReadAsyncCallback(apiBuffer, 40, sizeof(uint32_t), _, _))
         .WillOnce(InvokeWithoutArgs([&]() {
@@ -816,7 +829,7 @@
 TEST_F(WireBufferMappingTests, ErrorWhileMappingForRead) {
     dawnCallbackUserdata userdata = 8654;
     dawnBufferMapReadAsync(buffer, 40, sizeof(uint32_t), ToMockBufferMapReadCallback, userdata);
-    
+
     EXPECT_CALL(api, OnBufferMapReadAsyncCallback(apiBuffer, 40, sizeof(uint32_t), _, _))
         .WillOnce(InvokeWithoutArgs([&]() {
             api.CallMapReadCallback(apiBuffer, DAWN_BUFFER_MAP_ASYNC_STATUS_ERROR, nullptr);
@@ -1163,3 +1176,211 @@
 
     FlushClient();
 }
+
+class WireFenceTests : public WireTestsBase {
+  public:
+    WireFenceTests() : WireTestsBase(true) {
+    }
+
+    void SetUp() override {
+        WireTestsBase::SetUp();
+
+        {
+            dawnFenceDescriptor descriptor;
+            descriptor.initialValue = 1;
+            descriptor.nextInChain = nullptr;
+
+            apiFence = api.GetNewFence();
+            fence = dawnDeviceCreateFence(device, &descriptor);
+
+            EXPECT_CALL(api, DeviceCreateFence(apiDevice, _)).WillOnce(Return(apiFence));
+            FlushClient();
+        }
+        {
+            queue = dawnDeviceCreateQueue(device);
+            apiQueue = api.GetNewQueue();
+            EXPECT_CALL(api, DeviceCreateQueue(apiDevice)).WillOnce(Return(apiQueue));
+            FlushClient();
+        }
+    }
+
+  protected:
+    void DoQueueSignal(uint64_t signalValue) {
+        dawnQueueSignal(queue, fence, signalValue);
+        EXPECT_CALL(api, QueueSignal(apiQueue, apiFence, signalValue)).Times(1);
+
+        // This callback is generated to update the completedValue of the fence
+        // on the client
+        EXPECT_CALL(api, OnFenceOnCompletionCallback(apiFence, signalValue, _, _))
+            .WillOnce(InvokeWithoutArgs([&]() {
+                api.CallFenceOnCompletionCallback(apiFence, DAWN_FENCE_COMPLETION_STATUS_SUCCESS);
+            }));
+    }
+
+    // A successfully created fence
+    dawnFence fence;
+    dawnFence apiFence;
+
+    dawnQueue queue;
+    dawnQueue apiQueue;
+};
+
+// Check that signaling a fence succeeds
+TEST_F(WireFenceTests, QueueSignalSuccess) {
+    DoQueueSignal(2u);
+    DoQueueSignal(3u);
+    FlushClient();
+    FlushServer();
+}
+
+// Without any flushes, it is valid to signal a value greater than the current
+// signaled value
+TEST_F(WireFenceTests, QueueSignalSynchronousValidationSuccess) {
+    dawnCallbackUserdata userdata = 9157;
+    dawnDeviceSetErrorCallback(device, ToMockDeviceErrorCallback, userdata);
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(0);
+
+    dawnQueueSignal(queue, fence, 2u);
+    dawnQueueSignal(queue, fence, 4u);
+    dawnQueueSignal(queue, fence, 5u);
+}
+
+// Without any flushes, errors should be generated when signaling a value less
+// than or equal to the current signaled value
+TEST_F(WireFenceTests, QueueSignalSynchronousValidationError) {
+    dawnCallbackUserdata userdata = 3157;
+    dawnDeviceSetErrorCallback(device, ToMockDeviceErrorCallback, userdata);
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(1);
+    dawnQueueSignal(queue, fence, 0u);  // Error
+    EXPECT_TRUE(Mock::VerifyAndClear(mockDeviceErrorCallback.get()));
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(1);
+    dawnQueueSignal(queue, fence, 1u);  // Error
+    EXPECT_TRUE(Mock::VerifyAndClear(mockDeviceErrorCallback.get()));
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(0);
+    dawnQueueSignal(queue, fence, 4u);  // Success
+    EXPECT_TRUE(Mock::VerifyAndClear(mockDeviceErrorCallback.get()));
+
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata)).Times(1);
+    dawnQueueSignal(queue, fence, 3u);  // Error
+    EXPECT_TRUE(Mock::VerifyAndClear(mockDeviceErrorCallback.get()));
+}
+
+// Check that callbacks are immediately called if the fence is already finished
+TEST_F(WireFenceTests, OnCompletionImmediate) {
+    // Can call on value < (initial) signaled value happens immediately
+    {
+        dawnCallbackUserdata userdata = 9847;
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata))
+            .Times(1);
+        dawnFenceOnCompletion(fence, 0, ToMockFenceOnCompletionCallback, userdata);
+    }
+
+    // Can call on value == (initial) signaled value happens immediately
+    {
+        dawnCallbackUserdata userdata = 4347;
+        EXPECT_CALL(*mockFenceOnCompletionCallback,
+                    Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata))
+            .Times(1);
+        dawnFenceOnCompletion(fence, 1, ToMockFenceOnCompletionCallback, userdata);
+    }
+}
+
+// Check that all passed client completion callbacks are called
+TEST_F(WireFenceTests, OnCompletionMultiple) {
+    DoQueueSignal(3u);
+    DoQueueSignal(6u);
+
+    dawnCallbackUserdata userdata0 = 2134;
+    dawnCallbackUserdata userdata1 = 7134;
+    dawnCallbackUserdata userdata2 = 3144;
+    dawnCallbackUserdata userdata3 = 1130;
+
+    // Add callbacks in a non-monotonic order. They should still be called
+    // in order of increasing fence value.
+    // Add multiple callbacks for the same value.
+    dawnFenceOnCompletion(fence, 6, ToMockFenceOnCompletionCallback, userdata0);
+    dawnFenceOnCompletion(fence, 2, ToMockFenceOnCompletionCallback, userdata1);
+    dawnFenceOnCompletion(fence, 3, ToMockFenceOnCompletionCallback, userdata2);
+    dawnFenceOnCompletion(fence, 2, ToMockFenceOnCompletionCallback, userdata3);
+
+    Sequence s1, s2;
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata1))
+        .Times(1)
+        .InSequence(s1);
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata3))
+        .Times(1)
+        .InSequence(s2);
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata2))
+        .Times(1)
+        .InSequence(s1, s2);
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, userdata0))
+        .Times(1)
+        .InSequence(s1, s2);
+
+    FlushClient();
+    FlushServer();
+}
+
+// Without any flushes, it is valid to wait on a value less than or equal to
+// the last signaled value
+TEST_F(WireFenceTests, OnCompletionSynchronousValidationSuccess) {
+    dawnQueueSignal(queue, fence, 4u);
+    dawnFenceOnCompletion(fence, 2u, ToMockFenceOnCompletionCallback, 0);
+    dawnFenceOnCompletion(fence, 3u, ToMockFenceOnCompletionCallback, 0);
+    dawnFenceOnCompletion(fence, 4u, ToMockFenceOnCompletionCallback, 0);
+}
+
+// Without any flushes, errors should be generated when waiting on a value greater
+// than the last signaled value
+TEST_F(WireFenceTests, OnCompletionSynchronousValidationError) {
+    dawnCallbackUserdata userdata1 = 3817;
+    dawnCallbackUserdata userdata2 = 3857;
+    dawnDeviceSetErrorCallback(device, ToMockDeviceErrorCallback, userdata2);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_ERROR, userdata1))
+        .Times(1);
+    EXPECT_CALL(*mockDeviceErrorCallback, Call(_, userdata2)).Times(1);
+
+    dawnFenceOnCompletion(fence, 2u, ToMockFenceOnCompletionCallback, userdata1);
+}
+
+// Check that the fence completed value is initialized
+TEST_F(WireFenceTests, GetCompletedValueInitialization) {
+    EXPECT_EQ(dawnFenceGetCompletedValue(fence), 1u);
+}
+
+// Check that the fence completed value updates after signaling the fence
+TEST_F(WireFenceTests, GetCompletedValueUpdate) {
+    DoQueueSignal(3u);
+    FlushClient();
+    FlushServer();
+
+    EXPECT_EQ(dawnFenceGetCompletedValue(fence), 3u);
+}
+
+// Check that the fence completed value does not update without a flush
+TEST_F(WireFenceTests, GetCompletedValueNoUpdate) {
+    dawnQueueSignal(queue, fence, 3u);
+    EXPECT_EQ(dawnFenceGetCompletedValue(fence), 1u);
+}
+
+// Check that the callback is called with UNKNOWN when the fence is destroyed
+// before the completed value is updated
+TEST_F(WireFenceTests, DestroyBeforeOnCompletionEnd) {
+    dawnCallbackUserdata userdata = 8616;
+    dawnQueueSignal(queue, fence, 3u);
+    dawnFenceOnCompletion(fence, 2u, ToMockFenceOnCompletionCallback, userdata);
+    EXPECT_CALL(*mockFenceOnCompletionCallback,
+                Call(DAWN_FENCE_COMPLETION_STATUS_UNKNOWN, userdata))
+        .Times(1);
+
+    dawnFenceRelease(fence);
+}
diff --git a/src/tests/unittests/validation/FenceValidationTests.cpp b/src/tests/unittests/validation/FenceValidationTests.cpp
new file mode 100644
index 0000000..5add1bc
--- /dev/null
+++ b/src/tests/unittests/validation/FenceValidationTests.cpp
@@ -0,0 +1,185 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "tests/unittests/validation/ValidationTest.h"
+
+#include <gmock/gmock.h>
+
+using namespace testing;
+
+class MockFenceOnCompletionCallback {
+  public:
+    MOCK_METHOD2(Call, void(dawnFenceCompletionStatus status, dawnCallbackUserdata userdata));
+};
+
+struct FenceOnCompletionExpectation {
+    dawn::Fence fence;
+    uint64_t value;
+    dawnFenceCompletionStatus status;
+};
+
+static std::unique_ptr<MockFenceOnCompletionCallback> mockFenceOnCompletionCallback;
+static void ToMockFenceOnCompletionCallback(dawnFenceCompletionStatus status,
+                                            dawnCallbackUserdata userdata) {
+    mockFenceOnCompletionCallback->Call(status, userdata);
+}
+
+class FenceValidationTest : public ValidationTest {
+  protected:
+    void TestOnCompletion(dawn::Fence fence, uint64_t value, dawnFenceCompletionStatus status) {
+        FenceOnCompletionExpectation* expectation = new FenceOnCompletionExpectation;
+        expectation->fence = fence;
+        expectation->value = value;
+        expectation->status = status;
+        dawnCallbackUserdata userdata =
+            static_cast<dawnCallbackUserdata>(reinterpret_cast<uintptr_t>(expectation));
+
+        EXPECT_CALL(*mockFenceOnCompletionCallback, Call(status, userdata)).Times(1);
+        fence.OnCompletion(value, ToMockFenceOnCompletionCallback, userdata);
+    }
+
+    void Flush() {
+        device.Tick();
+    }
+
+    dawn::Queue queue;
+
+  private:
+    void SetUp() override {
+        ValidationTest::SetUp();
+
+        mockFenceOnCompletionCallback = std::make_unique<MockFenceOnCompletionCallback>();
+        queue = device.CreateQueue();
+    }
+
+    void TearDown() override {
+        // Delete mocks so that expectations are checked
+        mockFenceOnCompletionCallback = nullptr;
+
+        ValidationTest::TearDown();
+    }
+};
+
+// Test cases where creation should succeed
+TEST_F(FenceValidationTest, CreationSuccess) {
+    // Success
+    {
+        dawn::FenceDescriptor descriptor;
+        descriptor.initialValue = 0;
+        device.CreateFence(&descriptor);
+    }
+}
+
+TEST_F(FenceValidationTest, GetCompletedValue) {
+    // Starts at initial value
+    {
+        dawn::FenceDescriptor descriptor;
+        descriptor.initialValue = 1;
+        dawn::Fence fence = device.CreateFence(&descriptor);
+        EXPECT_EQ(fence.GetCompletedValue(), 1u);
+    }
+}
+
+// Test that OnCompletion handlers are called immediately for
+// already completed fence values
+TEST_F(FenceValidationTest, OnCompletionImmediate) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 0))
+        .Times(1);
+    fence.OnCompletion(0u, ToMockFenceOnCompletionCallback, 0);
+
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 1))
+        .Times(1);
+    fence.OnCompletion(1u, ToMockFenceOnCompletionCallback, 1);
+}
+
+// Test setting OnCompletion handlers for values > signaled value
+TEST_F(FenceValidationTest, OnCompletionLargerThanSignaled) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    // Cannot signal for values > signaled value
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_ERROR, 0))
+        .Times(1);
+    ASSERT_DEVICE_ERROR(fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0));
+
+    // Can set handler after signaling
+    queue.Signal(fence, 2);
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 0))
+        .Times(1);
+    fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0);
+
+    Flush();
+}
+
+TEST_F(FenceValidationTest, GetCompletedValueInsideCallback) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    queue.Signal(fence, 3);
+    fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0);
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 0))
+        .WillOnce(Invoke([&](dawnFenceCompletionStatus status, dawnCallbackUserdata userdata) {
+            EXPECT_EQ(fence.GetCompletedValue(), 3u);
+        }));
+
+    Flush();
+}
+
+TEST_F(FenceValidationTest, GetCompletedValueAfterCallback) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    queue.Signal(fence, 2);
+    fence.OnCompletion(2u, ToMockFenceOnCompletionCallback, 0);
+    EXPECT_CALL(*mockFenceOnCompletionCallback, Call(DAWN_FENCE_COMPLETION_STATUS_SUCCESS, 0))
+        .Times(1);
+
+    Flush();
+    EXPECT_EQ(fence.GetCompletedValue(), 2u);
+}
+
+TEST_F(FenceValidationTest, SignalError) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    // value < fence signaled value
+    ASSERT_DEVICE_ERROR(queue.Signal(fence, 0));
+
+    // value == fence signaled value
+    ASSERT_DEVICE_ERROR(queue.Signal(fence, 1));
+}
+
+TEST_F(FenceValidationTest, SignalSuccess) {
+    dawn::FenceDescriptor descriptor;
+    descriptor.initialValue = 1;
+    dawn::Fence fence = device.CreateFence(&descriptor);
+
+    // Success
+    queue.Signal(fence, 2);
+    Flush();
+    EXPECT_EQ(fence.GetCompletedValue(), 2u);
+
+    // Success increasing fence value by more than 1
+    queue.Signal(fence, 6);
+    Flush();
+    EXPECT_EQ(fence.GetCompletedValue(), 6u);
+}