diff --git a/docs/aidl-cpp.md b/docs/aidl-cpp.md
index 65cc8e4..156b697 100644
--- a/docs/aidl-cpp.md
+++ b/docs/aidl-cpp.md
@@ -91,6 +91,7 @@
 | String                | String16            | in    | Supports null references.                             |
 | @utf8InCpp String     | std::string         | in    | @utf8InCpp causes UTF16 to UTF8 conversion in C++.    |
 | android.os.Parcelable | android::Parcelable | inout |                                                       |
+| java.util.Map         | android::binder::Map| inout | `std::map<std::string,android::binder::Value>`        |
 | T extends IBinder     | sp<T>               | in    |                                                       |
 | Arrays (T[])          | vector<T>           | inout | May contain only primitives, Strings and parcelables. |
 | List<String>          | vector<String16>    | inout |                                                       |
@@ -98,12 +99,6 @@
 | List<IBinder>         | vector<sp<IBinder>> | inout |                                                       |
 | FileDescriptor        | unique_fd           | inout | android-base/unique_fd.h from libbase                 |
 
-Note that java.util.Map and java.utils.List are not good candidates for cross
-language communication because they may contain arbitrary types on the Java
-side.  For instance, Map is cast to Map<String,Object> and then the object
-values dynamically inspected and serialized as type/value pairs.  Support
-exists for sending arbitrary Java serializables, Android Bundles, etc.
-
 Note that annotations may be placed at the interface level, as well as on a
 type by type basis.  Interface level annotations will be applied
 opportunistically and be overridden by per type annotations.  For instance, an
diff --git a/generate_java_binder.cpp b/generate_java_binder.cpp
index 02a6922..2d2ba68 100644
--- a/generate_java_binder.cpp
+++ b/generate_java_binder.cpp
@@ -332,6 +332,8 @@
     realCall->arguments.push_back(v);
   }
 
+  cl = NULL;
+
   // the real call
   Variable* _result = NULL;
   if (method.GetType().GetName() == "void") {
diff --git a/tests/aidl_test_client_primitives.cpp b/tests/aidl_test_client_primitives.cpp
index 6f70f43..528d3ba 100644
--- a/tests/aidl_test_client_primitives.cpp
+++ b/tests/aidl_test_client_primitives.cpp
@@ -21,6 +21,8 @@
 
 #include <utils/String16.h>
 #include <utils/String8.h>
+#include <binder/Value.h>
+#include <binder/Map.h>
 
 #include "android/aidl/tests/INamedCallback.h"
 
@@ -33,6 +35,8 @@
 
 // libbinder:
 using android::binder::Status;
+using android::binder::Value;
+using android::binder::Map;
 
 // generated
 using android::aidl::tests::ITestService;
@@ -51,6 +55,11 @@
 bool ConfirmPrimitiveRepeat(const sp<ITestService>& s) {
   cout << "Confirming passing and returning primitives works." << endl;
 
+  Map test_map;
+  test_map["first_val"] = int8_t{-128};
+  test_map["second_val"] = int32_t{1 << 30};
+  test_map["third_val"] = String16("OHAI");
+
   if (!RepeatPrimitive(s, &ITestService::RepeatBoolean, true) ||
       !RepeatPrimitive(s, &ITestService::RepeatByte, int8_t{-128}) ||
       !RepeatPrimitive(s, &ITestService::RepeatChar, char16_t{'A'}) ||
@@ -58,6 +67,7 @@
       !RepeatPrimitive(s, &ITestService::RepeatLong, int64_t{1ll << 60}) ||
       !RepeatPrimitive(s, &ITestService::RepeatFloat, float{1.0f/3.0f}) ||
       !RepeatPrimitive(s, &ITestService::RepeatDouble, double{1.0/3.0}) ||
+      !RepeatPrimitive(s, &ITestService::RepeatMap, test_map) ||
       !RepeatPrimitive(
           s, &ITestService::RepeatInt, ITestService::TEST_CONSTANT)  ||
       !RepeatPrimitive(
diff --git a/tests/aidl_test_service.cpp b/tests/aidl_test_service.cpp
index 9e2304e..abea6ae 100644
--- a/tests/aidl_test_service.cpp
+++ b/tests/aidl_test_service.cpp
@@ -27,6 +27,7 @@
 #include <binder/IServiceManager.h>
 #include <binder/ProcessState.h>
 #include <binder/Status.h>
+#include <binder/Value.h>
 #include <utils/Errors.h>
 #include <utils/Log.h>
 #include <utils/Looper.h>
@@ -67,6 +68,7 @@
 using android::aidl::tests::INamedCallback;
 using android::aidl::tests::SimpleParcelable;
 using android::os::PersistableBundle;
+using android::binder::Map;
 
 // Standard library
 using std::map;
@@ -117,6 +119,10 @@
     ALOGI("Repeating token %s", token_str.str().c_str());
   }
 
+  void LogRepeatedMapToken(const Map& token) {
+    ALOGI("Repeating Map with %d elements", (int)token.size());
+  }
+
   Status RepeatBoolean(bool token, bool* _aidl_return) override {
     LogRepeatedToken(token ? 1 : 0);
     *_aidl_return = token;
@@ -157,6 +163,11 @@
     *_aidl_return = token;
     return Status::ok();
   }
+  Status RepeatMap(const Map& token, Map* _aidl_return) override {
+    LogRepeatedMapToken(token);
+    *_aidl_return = token;
+    return Status::ok();
+  }
 
   Status RepeatSimpleParcelable(const SimpleParcelable& input,
                                 SimpleParcelable* repeat,
diff --git a/tests/android/aidl/tests/ITestService.aidl b/tests/android/aidl/tests/ITestService.aidl
index 4de6925..91b13b4 100644
--- a/tests/android/aidl/tests/ITestService.aidl
+++ b/tests/android/aidl/tests/ITestService.aidl
@@ -47,6 +47,7 @@
   float RepeatFloat(float token);
   double RepeatDouble(double token);
   String RepeatString(String token);
+  Map RepeatMap(in Map token);
 
   SimpleParcelable RepeatSimpleParcelable(in SimpleParcelable input,
                                           out SimpleParcelable repeat);
diff --git a/tests/java_app/src/android/aidl/tests/TestServiceClient.java b/tests/java_app/src/android/aidl/tests/TestServiceClient.java
index 4af4aa0..4f4d462 100644
--- a/tests/java_app/src/android/aidl/tests/TestServiceClient.java
+++ b/tests/java_app/src/android/aidl/tests/TestServiceClient.java
@@ -38,6 +38,8 @@
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
+import java.util.Map;
+import java.util.HashMap;
 
 // Generated
 import android.aidl.tests.INamedCallback;
@@ -154,6 +156,17 @@
                                      " responded " + response);
                 }
             }
+            {
+                Map<String, Object> query = new HashMap<String, Object>();
+                query.put("first_val", new Byte((byte)-128));
+                query.put("second_val", new Integer(1<<30));
+                query.put("third_val", "OHAI");
+                Object response = service.RepeatMap(query);
+                if (!query.equals(response)) {
+                    mLog.logAndThrow("Repeat with " + query +
+                                     " responded " + response);
+                }
+            }
 
             List<String> queries = Arrays.asList(
                 "not empty", "", "\0",
diff --git a/tests/test_helpers.h b/tests/test_helpers.h
index 7d5145b..b4f0084 100644
--- a/tests/test_helpers.h
+++ b/tests/test_helpers.h
@@ -28,12 +28,12 @@
 namespace tests {
 namespace client {
 
-template <typename T, typename U>
+template <typename T, typename U, typename V>
 bool RepeatPrimitive(
     const android::sp<android::aidl::tests::ITestService>& service,
-    android::binder::Status(android::aidl::tests::ITestService::*func)(T, T*),
+    android::binder::Status(android::aidl::tests::ITestService::*func)(T, V*),
     U input) {
-  T reply;
+  V reply;
   android::binder::Status status = (*service.*func)(input, &reply);
   if (!status.isOk() || input != reply) {
     LOG(ERROR) << "Failed to repeat primitive. status=" << status.toString8()
diff --git a/type_cpp.cpp b/type_cpp.cpp
index e20f603..2ac1523 100644
--- a/type_cpp.cpp
+++ b/type_cpp.cpp
@@ -265,6 +265,36 @@
   }
 };
 
+class NullableMap : public Type {
+ public:
+  NullableMap()
+      : Type(ValidatableType::KIND_BUILT_IN,
+             "java.util", "Map",
+             {"binder/Map.h", "binder/Value.h"},
+             "::std::unique_ptr<::android::binder::Map>",
+             "readNullableMap", "writeNullableMap") {}
+  virtual ~NullableMap() = default;
+  bool CanBeOutParameter() const override { return true; }
+};
+
+
+class MapType : public Type {
+ public:
+  MapType()
+      : Type(ValidatableType::KIND_BUILT_IN,
+             "java.util", "Map",
+             {"binder/Map.h","binder/Value.h"},
+             "::android::binder::Map",
+             "readMap", "writeMap",
+             kNoArrayType,
+             new NullableMap() ) {}
+  virtual ~MapType() = default;
+  bool CanBeOutParameter() const override { return true; }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(MapType);
+};  // class MapType
+
 class NullableStringListType : public Type {
  public:
   NullableStringListType()
@@ -457,6 +487,8 @@
       kNoArrayType, nullable_ibinder);
   Add(ibinder_type_);
 
+  Add(new MapType());
+
   Add(new BinderListType());
   Add(new StringListType());
   Add(new Utf8InCppStringListType());